

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    
    <title>fatghol.rg &mdash; FatGHoL v5.4 documentation</title>
    <link rel="stylesheet" href="../../_static/default.css" type="text/css" />
    <link rel="stylesheet" href="../../_static/pygments.css" type="text/css" />
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    '../../',
        VERSION:     '5.4',
        COLLAPSE_INDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  true
      };
    </script>
    <script type="text/javascript" src="../../_static/jquery.js"></script>
    <script type="text/javascript" src="../../_static/underscore.js"></script>
    <script type="text/javascript" src="../../_static/doctools.js"></script>
    <link rel="top" title="FatGHoL v5.4 documentation" href="../../index.html" />
    <link rel="up" title="Module code" href="../index.html" />
 
<script type="text/javascript">
  var _gaq = _gaq || [];
  _gaq.push(['_setAccount', 'UA-23673826-1']);
  _gaq.push(['_trackPageview']);
</script>

  </head>
  <body>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li><a href="../../index.html">FatGHoL v5.4 documentation</a> &raquo;</li>
          <li><a href="../index.html" accesskey="U">Module code</a> &raquo;</li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <h1>Source code for fatghol.rg</h1><div class="highlight"><pre>
<span class="c">#! /usr/bin/env python</span>
<span class="c">#</span>
<span class="sd">&quot;&quot;&quot;Classes and functions to deal with fatgraphs.</span>
<span class="sd">&quot;&quot;&quot;</span>
<span class="c">#</span>
<span class="c">#   Copyright (C) 2008-2012 Riccardo Murri &lt;riccardo.murri@gmail.com&gt;</span>
<span class="c">#   All rights reserved.</span>
<span class="c">#</span>
<span class="c">#   This program is free software: you can redistribute it and/or modify</span>
<span class="c">#   it under the terms of the GNU General Public License as published by</span>
<span class="c">#   the Free Software Foundation, either version 3 of the License, or</span>
<span class="c">#   (at your option) any later version.</span>
<span class="c">#</span>
<span class="c">#   This program is distributed in the hope that it will be useful,</span>
<span class="c">#   but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<span class="c">#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the</span>
<span class="c">#   GNU General Public License for more details.</span>
<span class="c">#</span>
<span class="c">#   You should have received a copy of the GNU General Public License</span>
<span class="c">#   along with this program.  If not, see &lt;http://www.gnu.org/licenses/&gt;.</span>
<span class="c">#</span>
<span class="n">__docformat__</span> <span class="o">=</span> <span class="s">&#39;reStructuredText&#39;</span>


<span class="c">#import cython</span>

<span class="c">## stdlib imports</span>

<span class="kn">from</span> <span class="nn">collections</span> <span class="kn">import</span> <span class="n">defaultdict</span><span class="p">,</span> <span class="n">Iterator</span>
<span class="kn">import</span> <span class="nn">logging</span>
<span class="kn">import</span> <span class="nn">os.path</span>

<span class="c">## application-local imports</span>

<span class="kn">import</span> <span class="nn">fatghol</span>
<span class="kn">from</span> <span class="nn">fatghol.cache</span> <span class="kn">import</span> <span class="p">(</span>
    <span class="n">Caching</span><span class="p">,</span>
    <span class="n">ocache0</span><span class="p">,</span>
    <span class="n">ocache_contract</span><span class="p">,</span>
    <span class="n">ocache_eq</span><span class="p">,</span>
    <span class="n">ocache_isomorphisms</span><span class="p">,</span>
    <span class="p">)</span>
<span class="kn">from</span> <span class="nn">fatghol.combinatorics</span> <span class="kn">import</span> <span class="n">Permutation</span>
<span class="kn">from</span> <span class="nn">fatghol.cyclicseq</span> <span class="kn">import</span> <span class="n">CyclicList</span><span class="p">,</span> <span class="n">CyclicTuple</span>
<span class="kn">from</span> <span class="nn">fatghol.iterators</span> <span class="kn">import</span> <span class="p">(</span>
    <span class="n">BufferingIterator</span><span class="p">,</span>
    <span class="p">)</span>
<span class="kn">from</span> <span class="nn">fatghol.loadsave</span> <span class="kn">import</span> <span class="n">load</span><span class="p">,</span> <span class="n">save</span>
<span class="kn">from</span> <span class="nn">fatghol.runtime</span> <span class="kn">import</span> <span class="n">runtime</span>
<span class="kn">import</span> <span class="nn">fatghol.timing</span> <span class="kn">as</span> <span class="nn">timing</span>
<span class="kn">from</span> <span class="nn">fatghol.utils</span> <span class="kn">import</span> <span class="p">(</span>
    <span class="n">concat</span><span class="p">,</span>
    <span class="n">ltranslate</span><span class="p">,</span>
    <span class="n">maybe</span><span class="p">,</span>
    <span class="n">sign</span><span class="p">,</span>
    <span class="p">)</span>


<span class="c">## main</span>

<div class="viewcode-block" id="BoundaryCycle"><a class="viewcode-back" href="../../api.html#fatghol.rg.BoundaryCycle">[docs]</a><span class="k">class</span> <span class="nc">BoundaryCycle</span><span class="p">(</span><span class="nb">frozenset</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;A boundary cycle of a Fatgraph.</span>

<span class="sd">    Boundary cycles are a cyclic sequence of &#39;corners&#39;: a corner</span>
<span class="sd">    consists of a vertex `v` and (an unordered pair of) two</span>
<span class="sd">    consecutive indices (in the cyclic order at `v`, so, either</span>
<span class="sd">    `j == i+1` or `i` and `j` are the starting and ending indices).</span>

<span class="sd">    Two boundary cycles are equal if they comprise the same</span>
<span class="sd">    corners.</span>

<span class="sd">    A `BoundaryCycle` instance is constructed from a sequence of</span>
<span class="sd">    triples `(v, i, j)`, where `i` and `j` are consecutive (in the</span>
<span class="sd">    cyclic order sense) indices at a vertex `v`.  (Although no check</span>
<span class="sd">    is performed in the constructor code.)</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">__slots__</span> <span class="o">=</span> <span class="p">()</span>

    <span class="c"># no code to be added to the `frozenset` base class</span>
    <span class="k">pass</span>

</div>
<div class="viewcode-block" id="Vertex"><a class="viewcode-back" href="../../api.html#fatghol.rg.Vertex">[docs]</a><span class="k">class</span> <span class="nc">Vertex</span><span class="p">(</span><span class="n">CyclicList</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;A (representative of) a vertex of a ribbon graph.</span>

<span class="sd">    A vertex is represented by the cyclically ordered list of its</span>
<span class="sd">    (decorated) edges.  The edge colorings may be accessed through a</span>
<span class="sd">    (read-only) sequence interface.</span>

<span class="sd">    At init time, the number of loops attached to this vertex is</span>
<span class="sd">    computed and stored in the `.num_loops` attribute::</span>

<span class="sd">      &gt;&gt;&gt; Vertex([0,1,2]).num_loops</span>
<span class="sd">      0</span>
<span class="sd">      &gt;&gt;&gt; Vertex([1,1,0,0]).num_loops</span>
<span class="sd">      2</span>
<span class="sd">    &quot;&quot;&quot;</span>
    <span class="c"># FIXME: reimplement `Vertex` as a `tuple`/`CyclicTuple` subclass.</span>

    <span class="n">__slots__</span> <span class="o">=</span> <span class="p">(</span> <span class="s">&#39;num_loops&#39;</span> <span class="p">)</span>

    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">seq</span><span class="p">):</span>
        <span class="n">CyclicList</span><span class="o">.</span><span class="n">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">seq</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">num_loops</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">-</span> <span class="nb">len</span><span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="bp">self</span><span class="p">))</span>

    <span class="k">def</span> <span class="nf">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>


</div>
<div class="viewcode-block" id="Edge"><a class="viewcode-back" href="../../api.html#fatghol.rg.Edge">[docs]</a><span class="k">class</span> <span class="nc">Edge</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;An edge of a fatgraph.</span>

<span class="sd">    An edge is represented by its two endpoints; each endpoint has the form</span>
<span class="sd">    `(v_idx, a_idx)`, where:</span>
<span class="sd">      - `v_idx` is the index of the endpoint vertex (within the fatgraph), and</span>
<span class="sd">      - `a_idx` is the index at which this edge appears within the vertex `v_idx`.</span>

<span class="sd">    It is guaranteed that endpoints are stored in increasing vertex</span>
<span class="sd">    index order::</span>

<span class="sd">      &gt;&gt;&gt; x = Edge((3, 0), (1, 2))</span>
<span class="sd">      &gt;&gt;&gt; x.endpoints</span>
<span class="sd">      ((1, 2), (3, 0))</span>
<span class="sd">      &gt;&gt;&gt; x.endpoints[0][0] &lt; x.endpoints[1][0]</span>
<span class="sd">      True</span>

<span class="sd">    `Edge` objects bear no reference to a particular `Fatgraph`</span>
<span class="sd">    instance, to allow sharing the same edge instance among</span>
<span class="sd">    `Fatgraph`s that are created by contraction or other geometrical</span>
<span class="sd">    operations.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">__slots__</span> <span class="o">=</span> <span class="p">(</span> <span class="s">&#39;endpoints&#39;</span> <span class="p">)</span>
    
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">va1</span><span class="p">,</span> <span class="n">va2</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">va1</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">va2</span><span class="p">[</span><span class="mi">0</span><span class="p">]:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">endpoints</span> <span class="o">=</span> <span class="p">(</span><span class="n">va1</span><span class="p">,</span> <span class="n">va2</span><span class="p">)</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">endpoints</span> <span class="o">=</span> <span class="p">(</span><span class="n">va2</span><span class="p">,</span> <span class="n">va1</span><span class="p">)</span>

<div class="viewcode-block" id="Edge.is_loop"><a class="viewcode-back" href="../../api.html#fatghol.rg.Edge.is_loop">[docs]</a>    <span class="k">def</span> <span class="nf">is_loop</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return `True` if this `Edge` instance represents looping edge.</span>

<span class="sd">        Examples::</span>

<span class="sd">          &gt;&gt;&gt; Edge((0, 1), (0, 2)).is_loop()</span>
<span class="sd">          True</span>
<span class="sd">          &gt;&gt;&gt; Edge((0, 1), (1, 3)).is_loop()</span>
<span class="sd">          False</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span>
        </div>
<div class="viewcode-block" id="Edge.meets"><a class="viewcode-back" href="../../api.html#fatghol.rg.Edge.meets">[docs]</a>    <span class="k">def</span> <span class="nf">meets</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">v</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return `True` if vertex `v` is one of the endpoints.</span>

<span class="sd">        Example::</span>

<span class="sd">          &gt;&gt;&gt; x = Edge((3, 1), (1, 2))</span>
<span class="sd">          &gt;&gt;&gt; x.meets(3)</span>
<span class="sd">          True</span>
<span class="sd">          &gt;&gt;&gt; x.meets(1)</span>
<span class="sd">          True</span>
<span class="sd">          &gt;&gt;&gt; x.meets(0)</span>
<span class="sd">          False          </span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="p">(</span><span class="n">v</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span> <span class="ow">or</span> <span class="p">(</span><span class="n">v</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span>
</div>
<div class="viewcode-block" id="Edge.other_end"><a class="viewcode-back" href="../../api.html#fatghol.rg.Edge.other_end">[docs]</a>    <span class="k">def</span> <span class="nf">other_end</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">a</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return the endpoint opposed to `(v, a)`.</span>

<span class="sd">        Example::</span>

<span class="sd">          &gt;&gt;&gt; l = Edge((0, 1), (1, 3))</span>
<span class="sd">          &gt;&gt;&gt; l.other_end(0,1)</span>
<span class="sd">          (1, 3)</span>
<span class="sd">          &gt;&gt;&gt; l.other_end(1,3)</span>
<span class="sd">          (0, 1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">==</span> <span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">a</span><span class="p">):</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>

</div></div>
<div class="viewcode-block" id="Isomorphism"><a class="viewcode-back" href="../../api.html#fatghol.rg.Isomorphism">[docs]</a><span class="k">class</span> <span class="nc">Isomorphism</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;An isomorphism of `Fatgraphs`.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">__slots__</span> <span class="o">=</span> <span class="p">(</span>
        <span class="s">&#39;pe&#39;</span><span class="p">,</span>
        <span class="s">&#39;pv&#39;</span><span class="p">,</span>
        <span class="s">&#39;rot&#39;</span><span class="p">,</span>
        <span class="s">&#39;source&#39;</span><span class="p">,</span>
        <span class="s">&#39;target&#39;</span><span class="p">,</span>
        <span class="p">)</span>
    
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="p">,</span> <span class="n">pv</span><span class="p">,</span> <span class="n">rot</span><span class="p">,</span> <span class="n">pe</span><span class="p">):</span>
        <span class="c"># sanity checks</span>
        <span class="k">assert</span> <span class="nb">len</span><span class="p">(</span><span class="n">pv</span><span class="p">)</span> <span class="o">==</span> <span class="n">source</span><span class="o">.</span><span class="n">num_vertices</span>
        <span class="k">assert</span> <span class="nb">len</span><span class="p">(</span><span class="n">pv</span><span class="p">)</span> <span class="o">==</span> <span class="n">target</span><span class="o">.</span><span class="n">num_vertices</span>
        <span class="k">assert</span> <span class="nb">len</span><span class="p">(</span><span class="n">pe</span><span class="p">)</span> <span class="o">==</span> <span class="n">source</span><span class="o">.</span><span class="n">num_edges</span>
        <span class="k">assert</span> <span class="nb">len</span><span class="p">(</span><span class="n">pe</span><span class="p">)</span> <span class="o">==</span> <span class="n">target</span><span class="o">.</span><span class="n">num_edges</span>
        <span class="k">assert</span> <span class="nb">set</span><span class="p">(</span><span class="n">pv</span><span class="o">.</span><span class="n">keys</span><span class="p">())</span> <span class="o">==</span> <span class="nb">set</span><span class="p">(</span><span class="nb">range</span><span class="p">(</span><span class="n">source</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">))</span>
        <span class="k">assert</span> <span class="nb">set</span><span class="p">(</span><span class="n">pv</span><span class="o">.</span><span class="n">values</span><span class="p">())</span> <span class="o">==</span> <span class="nb">set</span><span class="p">(</span><span class="nb">range</span><span class="p">(</span><span class="n">target</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">)),</span> \
               <span class="p">(</span><span class="s">&quot;Got pv.values=</span><span class="si">%r</span><span class="s"> but target.num_vertices=</span><span class="si">%r</span><span class="s">&quot;</span>
                <span class="s">&quot; (and target=</span><span class="si">%r</span><span class="s">): number of elements do not match!&quot;</span>
                <span class="o">%</span> <span class="p">(</span><span class="n">pv</span><span class="o">.</span><span class="n">values</span><span class="p">(),</span> <span class="n">target</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">,</span> <span class="n">target</span><span class="p">))</span>
        <span class="k">assert</span> <span class="nb">set</span><span class="p">(</span><span class="n">pe</span><span class="o">.</span><span class="n">keys</span><span class="p">())</span> <span class="o">==</span> <span class="nb">set</span><span class="p">(</span><span class="nb">range</span><span class="p">(</span><span class="n">source</span><span class="o">.</span><span class="n">num_edges</span><span class="p">))</span>
        <span class="k">assert</span> <span class="nb">set</span><span class="p">(</span><span class="n">pe</span><span class="o">.</span><span class="n">values</span><span class="p">())</span> <span class="o">==</span> <span class="nb">set</span><span class="p">(</span><span class="nb">range</span><span class="p">(</span><span class="n">target</span><span class="o">.</span><span class="n">num_edges</span><span class="p">))</span>

        <span class="bp">self</span><span class="o">.</span><span class="n">source</span> <span class="o">=</span> <span class="n">source</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">target</span> <span class="o">=</span> <span class="n">target</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">pe</span> <span class="o">=</span> <span class="n">pe</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">rot</span> <span class="o">=</span> <span class="n">rot</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">pv</span> <span class="o">=</span> <span class="n">pv</span>

    <span class="k">def</span> <span class="nf">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="s">&quot;(</span><span class="si">%s</span><span class="s">, </span><span class="si">%s</span><span class="s">, </span><span class="si">%s</span><span class="s">)&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">pv</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">rot</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">pe</span><span class="p">)</span>

<div class="viewcode-block" id="Isomorphism.compare_orientations"><a class="viewcode-back" href="../../api.html#fatghol.rg.Isomorphism.compare_orientations">[docs]</a>    <span class="k">def</span> <span class="nf">compare_orientations</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return +1 or -1 depending on whether the orientations of</span>
<span class="sd">        the target Fatgraph pulls back to the orientation of the</span>
<span class="sd">        source Fatgraph via this `Isomorphism`.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">image_edge_numbering</span> <span class="o">=</span> <span class="n">Permutation</span><span class="p">((</span><span class="bp">self</span><span class="o">.</span><span class="n">source</span><span class="o">.</span><span class="n">edge_numbering</span><span class="p">[</span><span class="n">x</span><span class="p">],</span>
                                            <span class="bp">self</span><span class="o">.</span><span class="n">target</span><span class="o">.</span><span class="n">edge_numbering</span><span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">pe</span><span class="p">[</span><span class="n">x</span><span class="p">]])</span>
                                           <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">source</span><span class="o">.</span><span class="n">num_edges</span><span class="p">))</span>
        <span class="k">return</span> <span class="n">image_edge_numbering</span><span class="o">.</span><span class="n">sign</span><span class="p">()</span>
</div>
<div class="viewcode-block" id="Isomorphism.is_identity"><a class="viewcode-back" href="../../api.html#fatghol.rg.Isomorphism.is_identity">[docs]</a>    <span class="k">def</span> <span class="nf">is_identity</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Return `True` if this is the identity morphism.</span>

<span class="sd">        Only makes sense for automorphisms, so an `AssertionException`</span>
<span class="sd">        is raised if source and target differ.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="bp">self</span><span class="o">.</span><span class="n">source</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">target</span>
        <span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">pv</span><span class="p">)):</span>
            <span class="k">if</span> <span class="n">v</span> <span class="o">!=</span> <span class="bp">self</span><span class="o">.</span><span class="n">pv</span><span class="p">[</span><span class="n">v</span><span class="p">]:</span>
                <span class="k">return</span> <span class="bp">False</span>
            <span class="n">l</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">source</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v</span><span class="p">])</span>
            <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">rot</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">%</span> <span class="n">l</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">:</span>
                <span class="k">return</span> <span class="bp">False</span>
        <span class="k">for</span> <span class="n">e</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">pe</span><span class="p">)):</span>
            <span class="k">if</span> <span class="n">e</span> <span class="o">!=</span> <span class="bp">self</span><span class="o">.</span><span class="n">pe</span><span class="p">[</span><span class="n">e</span><span class="p">]:</span>
                <span class="k">return</span> <span class="bp">False</span>
        <span class="k">return</span> <span class="bp">True</span>
</div>
<div class="viewcode-block" id="Isomorphism.is_orientation_reversing"><a class="viewcode-back" href="../../api.html#fatghol.rg.Isomorphism.is_orientation_reversing">[docs]</a>    <span class="k">def</span> <span class="nf">is_orientation_reversing</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return `True` if this `Isomorphism` reverses orientation on</span>
<span class="sd">        the source and target `Fatgraph` instances.&quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="p">(</span><span class="o">-</span><span class="mi">1</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">compare_orientations</span><span class="p">())</span>
</div>
<div class="viewcode-block" id="Isomorphism.transform_boundary_cycle"><a class="viewcode-back" href="../../api.html#fatghol.rg.Isomorphism.transform_boundary_cycle">[docs]</a>    <span class="k">def</span> <span class="nf">transform_boundary_cycle</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">bcy</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return a new `BoundaryCycle` instance, obtained by</span>
<span class="sd">        transforming each corner according to a graph isomorphism.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">triples</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">)</span> <span class="ow">in</span> <span class="n">bcy</span><span class="p">:</span>
            <span class="n">l</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">source</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v</span><span class="p">])</span>
            <span class="c"># create transformed triple </span>
            <span class="n">v_</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">pv</span><span class="p">[</span><span class="n">v</span><span class="p">]</span>
            <span class="n">i_</span> <span class="o">=</span> <span class="p">(</span><span class="n">i</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">rot</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="o">%</span> <span class="n">l</span> <span class="c"># XXX: is it `-` or `+`?</span>
            <span class="n">j_</span> <span class="o">=</span> <span class="p">(</span><span class="n">j</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">rot</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="o">%</span> <span class="n">l</span>
            <span class="c"># ensure the contract is honored, that `j` is the</span>
            <span class="c"># index _following_ `i` in the cyclic order</span>
            <span class="k">if</span> <span class="n">i_</span> <span class="o">==</span> <span class="mi">0</span> <span class="ow">and</span> <span class="n">j_</span> <span class="o">==</span> <span class="n">l</span><span class="p">:</span>
                <span class="n">i_</span><span class="p">,</span> <span class="n">j_</span> <span class="o">=</span> <span class="n">j_</span><span class="p">,</span> <span class="n">i_</span>
            <span class="n">triples</span><span class="o">.</span><span class="n">append</span><span class="p">((</span><span class="n">v_</span><span class="p">,</span> <span class="n">i_</span><span class="p">,</span> <span class="n">j_</span><span class="p">))</span>
        <span class="k">return</span> <span class="n">BoundaryCycle</span><span class="p">(</span><span class="n">triples</span><span class="p">)</span>


</div></div>
<div class="viewcode-block" id="EqualIfIsomorphic"><a class="viewcode-back" href="../../api.html#fatghol.rg.EqualIfIsomorphic">[docs]</a><span class="k">class</span> <span class="nc">EqualIfIsomorphic</span><span class="p">(</span><span class="n">Caching</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;Instances of this class will compare equal if there is an</span>
<span class="sd">    isomorphism mapping one to the other.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">__slots__</span> <span class="o">=</span> <span class="p">(</span> <span class="s">&#39;invariants&#39;</span> <span class="p">)</span>


    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">invariants</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">invariants</span> <span class="o">=</span> <span class="n">invariants</span>
        <span class="c"># set this instance&#39;s ``persistent id&#39;&#39;</span>
        <span class="n">Caching</span><span class="o">.</span><span class="n">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

    
    <span class="nd">@ocache_eq</span>
    <span class="k">def</span> <span class="nf">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return `True` if `self` and `other` are isomorphic.&quot;&quot;&quot;</span>

        <span class="k">assert</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="p">)),</span> \
               <span class="s">&quot;EqualIfIsomorphic.__eq__:&quot;</span> \
               <span class="s">&quot; called with incompatible type arguments: `</span><span class="si">%s</span><span class="s">` and` </span><span class="si">%s</span><span class="s">`&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="p">),</span> <span class="nb">type</span><span class="p">(</span><span class="n">other</span><span class="p">))</span>

        <span class="c"># shortcuts</span>
        <span class="k">if</span> <span class="bp">self</span> <span class="ow">is</span> <span class="n">other</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">True</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">invariants</span> <span class="o">!=</span> <span class="n">other</span><span class="o">.</span><span class="n">invariants</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">False</span>

        <span class="c"># go the long way: try to find an explicit isomorphims</span>
        <span class="c"># between `self` and `other`</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="c"># if there is any morphism, then return `True`</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">isomorphisms</span><span class="p">(</span><span class="n">other</span><span class="p">)</span><span class="o">.</span><span class="n">next</span><span class="p">()</span>
            <span class="k">return</span> <span class="bp">True</span>
        <span class="k">except</span> <span class="ne">StopIteration</span><span class="p">:</span>
            <span class="c"># list of morphisms is empty, objects are not equal.</span>
            <span class="k">return</span> <span class="bp">False</span>


    <span class="c"># both `__eq__` and `__ne__` are needed for testing equality of objects;</span>
    <span class="c"># see `&lt;http://www.voidspace.org.uk/python/articles/comparison.shtml&gt;`</span>
    <span class="k">def</span> <span class="nf">__ne__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;The opposite of `__eq__` (which see).&quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="ow">not</span> <span class="bp">self</span><span class="o">.</span><span class="n">__eq__</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>


</div>
<div class="viewcode-block" id="Fatgraph"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph">[docs]</a><span class="k">class</span> <span class="nc">Fatgraph</span><span class="p">(</span><span class="n">EqualIfIsomorphic</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;A fully-decorated ribbon graph.</span>

<span class="sd">    Several attributes of this object are computed at init time and</span>
<span class="sd">    store characteristics of the fatgraph:</span>

<span class="sd">      `.boundary_cycles`</span>
<span class="sd">        List of the boundary components of this `Fatgraph` object.</span>
<span class="sd">        Each boundary component is represented by the list of</span>
<span class="sd">        (colored) edges.</span>

<span class="sd">      `.genus`</span>
<span class="sd">        The genus of the Riemann surface this fatgraph lies on.</span>
<span class="sd">      </span>
<span class="sd">      `.num_boundary_cycles`</span>
<span class="sd">        Number of boundary cycles of this `Fatgraph`.</span>

<span class="sd">      `.num_edges`</span>
<span class="sd">        The number of edges of this `Fatgraph` object.</span>

<span class="sd">      `.num_vertices`</span>
<span class="sd">        Number of vertices of this `Fatgraph` object.</span>

<span class="sd">      `.vertices`</span>
<span class="sd">        List of vertices of this `Fatgraph`; each one is an instance</span>
<span class="sd">        of the `Vertex` class; see `Fatgraph.__init__` for examples.</span>

<span class="sd">        </span>
<span class="sd">    Examples::</span>
<span class="sd">      &gt;&gt;&gt; Fatgraph([Vertex([2,1,0]), Vertex([2,1,0])]).num_boundary_cycles</span>
<span class="sd">      1</span>
<span class="sd">      &gt;&gt;&gt; Fatgraph([Vertex([2,1,0]), Vertex([2,0,1])]).num_boundary_cycles</span>
<span class="sd">      3</span>

<span class="sd">    Two `Fatgraph`s compare equal if they are isomorphic::</span>

<span class="sd">      &gt;&gt;&gt; Fatgraph([Vertex([1,0,0,1])]) == Fatgraph([Vertex([1,1,0,0])])</span>
<span class="sd">      True</span>

<span class="sd">      &gt;&gt;&gt; Fatgraph([Vertex([2,0,0]), Vertex([2,1,1])]) \</span>
<span class="sd">            == Fatgraph([Vertex([2,2,0]), Vertex([1,1,0])])</span>
<span class="sd">      True</span>

<span class="sd">      &gt;&gt;&gt; Fatgraph([Vertex([2,0,1]), Vertex([2,0,1])]) \</span>
<span class="sd">            == Fatgraph([Vertex([2,1,0]), Vertex([2,0,1])])</span>
<span class="sd">      False</span>

<span class="sd">      &gt;&gt;&gt; Fatgraph([Vertex([2,0,1]), Vertex([2,0,1])]) \</span>
<span class="sd">            == Fatgraph([Vertex([2,0,0]), Vertex([2,1,1])])</span>
<span class="sd">      False</span>

<span class="sd">      &gt;&gt;&gt; Fatgraph([Vertex([2,0,0]), Vertex([2,1,1])]) \</span>
<span class="sd">            == Fatgraph([Vertex([1,1,0,0])])</span>
<span class="sd">      False</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="n">__slots__</span> <span class="o">=</span> <span class="p">(</span>
        <span class="s">&#39;__weakref__&#39;</span><span class="p">,</span>
        <span class="s">&#39;boundary_cycles&#39;</span><span class="p">,</span>
        <span class="s">&#39;edges&#39;</span><span class="p">,</span>
        <span class="s">&#39;edge_numbering&#39;</span><span class="p">,</span>
        <span class="s">&#39;genus&#39;</span><span class="p">,</span>
        <span class="s">&#39;invariants&#39;</span><span class="p">,</span>
        <span class="s">&#39;num_boundary_cycles&#39;</span><span class="p">,</span>
        <span class="s">&#39;num_edges&#39;</span><span class="p">,</span>
        <span class="s">&#39;num_vertices&#39;</span><span class="p">,</span>
        <span class="s">&#39;vertices&#39;</span><span class="p">,</span>
        <span class="p">)</span>

    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">g_or_vs</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Construct a `Fatgraph` instance, taking list of vertices.</span>

<span class="sd">        Argument `g_or_vs` can be either:</span>

<span class="sd">          - a sequence of `Vertex` class instances::  </span>

<span class="sd">              &gt;&gt;&gt; g1 = Fatgraph([Vertex([2,0,1]), Vertex([2,1,0])])</span>

<span class="sd">            Note that the list of vertices is assigned, *not copied*</span>
<span class="sd">            into the instance variable.</span>

<span class="sd">        or:</span>

<span class="sd">          - another `Fatgraph` instance, in which case this acts as a</span>
<span class="sd">            copy-constructor (and any remaining arguments are</span>
<span class="sd">            ignored), returning a new `Fatgraph` instance::</span>

<span class="sd">              &gt;&gt;&gt; g2 = Fatgraph(g1)</span>
<span class="sd">              &gt;&gt;&gt; g2 is g1</span>
<span class="sd">              False</span>
<span class="sd">              &gt;&gt;&gt; g2 == g1</span>
<span class="sd">              True</span>

<span class="sd">            The returned `Fatgraph` instance *shares* all attributes</span>
<span class="sd">            with the instance given as argument::</span>

<span class="sd">              &gt;&gt;&gt; g2.vertices is g1.vertices</span>
<span class="sd">              True</span>
<span class="sd">              &gt;&gt;&gt; g2.edge_numbering is g1.edge_numbering</span>
<span class="sd">              True</span>
<span class="sd">              &gt;&gt;&gt; g2.edges is g1.edges</span>
<span class="sd">              True</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c"># dispatch based on type of arguments passed</span>
        <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">g_or_vs</span><span class="p">,</span> <span class="n">Fatgraph</span><span class="p">):</span>
            <span class="c"># copy-constructor used by class `NumberedFatgraph`</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">boundary_cycles</span> <span class="o">=</span> <span class="n">g_or_vs</span><span class="o">.</span><span class="n">boundary_cycles</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">edges</span> <span class="o">=</span> <span class="n">g_or_vs</span><span class="o">.</span><span class="n">edges</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">edge_numbering</span> <span class="o">=</span> <span class="n">g_or_vs</span><span class="o">.</span><span class="n">edge_numbering</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">genus</span> <span class="o">=</span> <span class="n">g_or_vs</span><span class="o">.</span><span class="n">genus</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">num_boundary_cycles</span> <span class="o">=</span> <span class="n">g_or_vs</span><span class="o">.</span><span class="n">num_boundary_cycles</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">=</span> <span class="n">g_or_vs</span><span class="o">.</span><span class="n">num_edges</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span> <span class="o">=</span> <span class="n">g_or_vs</span><span class="o">.</span><span class="n">num_vertices</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span> <span class="o">=</span> <span class="n">g_or_vs</span><span class="o">.</span><span class="n">vertices</span>

        <span class="k">else</span><span class="p">:</span> <span class="c"># initialize *new* instance</span>

            <span class="c">#: list of vertices</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span> <span class="o">=</span> <span class="n">g_or_vs</span>

            <span class="c">#: Number of edge colors</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">=</span> <span class="n">kwargs</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s">&#39;num_edges&#39;</span><span class="p">,</span>
                                        <span class="nb">sum</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">v</span><span class="p">)</span> <span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">)</span>

            <span class="c">#: Number of vertices  XXX: why is this settable with kwarg???</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span> <span class="o">=</span> <span class="n">kwargs</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s">&#39;num_vertices&#39;</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">g_or_vs</span><span class="p">))</span>

            <span class="k">if</span> <span class="s">&#39;edges&#39;</span> <span class="ow">in</span> <span class="n">kwargs</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">edges</span> <span class="o">=</span> <span class="n">kwargs</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s">&#39;edges&#39;</span><span class="p">)</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="c">#: Adjacency list of this graph.  For each edge, store a pair</span>
                <span class="c">#: `(v1, v2)` where `v1` and `v2` are (indices of)</span>
                <span class="c">#: endpoint vertices of an edge, and a corresponding pair</span>
                <span class="c">#: `(i1, i2)` where `i1` and `i2` are indices of the given</span>
                <span class="c">#: edge in vertices `v1` and `v2`.</span>
                <span class="c">#: Each pair `(v, i)` represents a flag by the endpoint</span>
                <span class="c">#: vertex and the index of the edge in the vertex.  (The</span>
                <span class="c">#: vertex index alone is not enough for representing the</span>
                <span class="c">#: edge arrow for loops.)</span>
                <span class="n">endpoints</span> <span class="o">=</span> <span class="p">[</span> <span class="p">[]</span> <span class="k">for</span> <span class="n">dummy</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span> <span class="p">]</span>
                <span class="k">for</span> <span class="n">current_vertex_index</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">):</span>
                    <span class="k">for</span> <span class="p">(</span><span class="n">edge_index_in_vertex</span><span class="p">,</span> <span class="n">edge</span><span class="p">)</span> \
                            <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">current_vertex_index</span><span class="p">]):</span>
                        <span class="k">assert</span> <span class="n">edge</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">),</span> \
                                   <span class="s">&quot;Fatgraph.__init__:&quot;</span>\
                                   <span class="s">&quot; edge number </span><span class="si">%d</span><span class="s"> not in range 0..</span><span class="si">%d</span><span class="s">&quot;</span> \
                                   <span class="o">%</span> <span class="p">(</span><span class="n">edge</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span>
                        <span class="n">endpoints</span><span class="p">[</span><span class="n">edge</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span> <span class="p">(</span><span class="n">current_vertex_index</span><span class="p">,</span> <span class="n">edge_index_in_vertex</span><span class="p">)</span> <span class="p">)</span>
                <span class="c"># now wrap endpoints into `Edge` objects</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">edges</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Edge</span><span class="p">(</span><span class="o">*</span><span class="n">e</span><span class="p">)</span> <span class="k">for</span> <span class="n">e</span> <span class="ow">in</span> <span class="n">endpoints</span> <span class="p">]</span>

            <span class="c">## Orientation is given by an ordering of the edges,</span>
            <span class="c">## which directly translates into an orientation of the</span>
            <span class="c">## associated cell.  </span>
            <span class="k">if</span> <span class="s">&#39;orientation&#39;</span> <span class="ow">in</span> <span class="n">kwargs</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">edge_numbering</span> <span class="o">=</span> <span class="n">kwargs</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s">&#39;orientation&#39;</span><span class="p">)</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">edge_numbering</span> <span class="o">=</span> <span class="p">[</span> <span class="n">x</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span> <span class="p">]</span>

            <span class="bp">self</span><span class="o">.</span><span class="n">boundary_cycles</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">compute_boundary_cycles</span><span class="p">()</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">num_boundary_cycles</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">boundary_cycles</span><span class="p">)</span>

            <span class="c"># by Euler, V-E+n=2-2*g</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">genus</span> <span class="o">=</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span>
                          <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_boundary_cycles</span> <span class="o">+</span> <span class="mi">2</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>

        <span class="c"># before computing invariants, check that internal data</span>
        <span class="c"># structures are in a consistent state</span>
        <span class="k">assert</span> <span class="bp">self</span><span class="o">.</span><span class="n">__ok</span><span class="p">()</span>

        <span class="c"># used for isomorphism testing</span>
        <span class="n">EqualIfIsomorphic</span><span class="o">.</span><span class="n">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="p">(</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">,</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">,</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">num_boundary_cycles</span><span class="p">,</span>
            <span class="p">))</span>


    <span class="k">def</span> <span class="nf">__ok</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Perform coherency checks on internal state variables of</span>
<span class="sd">        `Fatgraph` instance and return `True` if they all pass.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">,</span> \
               <span class="s">&quot;Fatgraph `</span><span class="si">%s</span><span class="s">` has 0 edges.&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="bp">self</span><span class="p">)</span>
        <span class="c"># check edge endpoints</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">edgeno</span><span class="p">,</span> <span class="n">edge</span><span class="p">)</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">edges</span><span class="p">):</span>
            <span class="k">assert</span> <span class="nb">len</span><span class="p">(</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">)</span> <span class="o">==</span> <span class="mi">2</span>
            <span class="k">assert</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="nb">tuple</span><span class="p">)</span>
            <span class="k">assert</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">],</span> <span class="nb">tuple</span><span class="p">)</span>
            <span class="k">assert</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="nb">int</span><span class="p">)</span>
            <span class="k">assert</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">1</span><span class="p">],</span> <span class="nb">int</span><span class="p">)</span>
            <span class="k">assert</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="nb">int</span><span class="p">)</span>
            <span class="k">assert</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">1</span><span class="p">],</span> <span class="nb">int</span><span class="p">)</span>
            <span class="k">assert</span> <span class="p">(</span><span class="mi">0</span> <span class="o">&lt;=</span> <span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">)</span>
            <span class="k">assert</span> <span class="p">(</span><span class="mi">0</span> <span class="o">&lt;=</span> <span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">)</span>
            <span class="k">assert</span> <span class="p">(</span><span class="mi">0</span> <span class="o">&lt;=</span> <span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span> <span class="o">&lt;</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]]))</span>
            <span class="k">assert</span> <span class="p">(</span><span class="mi">0</span> <span class="o">&lt;=</span> <span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span> <span class="o">&lt;</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">]]))</span>
            <span class="k">assert</span> <span class="p">(</span><span class="n">edgeno</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]]),</span> \
                    <span class="s">&quot;Invalid endpoint </span><span class="si">%s</span><span class="s"> for edge </span><span class="si">%d</span><span class="s"> of graph `</span><span class="si">%s</span><span class="s">`&quot;</span> \
                    <span class="o">%</span> <span class="p">(</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">edgeno</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span>
            <span class="k">assert</span> <span class="p">(</span><span class="n">edgeno</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">]]),</span> \
                    <span class="s">&quot;Invalid endpoint </span><span class="si">%s</span><span class="s"> for edge </span><span class="si">%d</span><span class="s"> of graph `</span><span class="si">%s</span><span class="s">`&quot;</span> \
                    <span class="o">%</span> <span class="p">(</span><span class="n">edge</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">],</span> <span class="n">edgeno</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span>
        <span class="c"># check that each edge occurs exactly two times in vertices</span>
        <span class="n">cnt</span> <span class="o">=</span> <span class="p">[</span> <span class="mi">0</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span> <span class="p">]</span>
        <span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">:</span>
            <span class="k">for</span> <span class="n">edgeno</span> <span class="ow">in</span> <span class="n">v</span><span class="p">:</span>
                <span class="n">cnt</span><span class="p">[</span><span class="n">edgeno</span><span class="p">]</span> <span class="o">+=</span> <span class="mi">1</span>
        <span class="k">for</span> <span class="n">edgeno</span><span class="p">,</span> <span class="n">cnt</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">cnt</span><span class="p">):</span>
            <span class="k">if</span> <span class="n">edgeno</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">:</span>
                <span class="k">assert</span> <span class="n">cnt</span> <span class="o">==</span> <span class="mi">2</span><span class="p">,</span> \
                       <span class="s">&quot;Regular edge </span><span class="si">%d</span><span class="s"> appears in </span><span class="si">%d</span><span class="s"> vertices&quot;</span> \
                       <span class="o">%</span> <span class="p">(</span><span class="n">edgeno</span><span class="p">,</span> <span class="n">cnt</span><span class="p">)</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="k">assert</span> <span class="n">cnt</span> <span class="o">==</span> <span class="mi">1</span><span class="p">,</span> \
                       <span class="s">&quot;External edge </span><span class="si">%d</span><span class="s"> appears in </span><span class="si">%d</span><span class="s"> vertices&quot;</span> \
                       <span class="o">%</span> <span class="p">(</span><span class="n">edgeno</span><span class="p">,</span> <span class="n">cnt</span><span class="p">)</span>

        <span class="k">assert</span> <span class="bp">self</span><span class="o">.</span><span class="n">edge_numbering</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span>
        
        <span class="k">return</span> <span class="bp">True</span>


    <span class="k">def</span> <span class="nf">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="nb">hasattr</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="s">&#39;vertices&#39;</span><span class="p">):</span>
            <span class="k">return</span> <span class="s">&quot;Fatgraph(&lt;Initializing...&gt;)&quot;</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">return</span> <span class="s">&quot;Fatgraph(</span><span class="si">%s</span><span class="s">)&quot;</span> <span class="o">%</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">)</span>

    
    <span class="k">def</span> <span class="nf">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>


<div class="viewcode-block" id="Fatgraph.automorphisms"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.automorphisms">[docs]</a>    <span class="k">def</span> <span class="nf">automorphisms</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Enumerate automorphisms of this `Fatgraph` object.</span>

<span class="sd">        See `.isomorphisms()` for details of how a `Fatgraph`</span>
<span class="sd">        isomorphism is represented.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">isomorphisms</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>


    <span class="c">#@cython.locals(vertices=list, corners=list,</span>
    <span class="c">#               v=cython.int, i=cython.int, corner=tuple)</span></div>
    <span class="nd">@staticmethod</span>
    <span class="k">def</span> <span class="nf">_first_unused_corner</span><span class="p">(</span><span class="n">vertices</span><span class="p">,</span> <span class="n">corners</span><span class="p">):</span>
        <span class="c"># fast-forward to the first unused corner</span>
        <span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">vertices</span><span class="p">)):</span>
            <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">vertices</span><span class="p">[</span><span class="n">v</span><span class="p">])):</span>
                <span class="n">corner</span> <span class="o">=</span> <span class="n">corners</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">i</span><span class="p">]</span>
                <span class="k">if</span> <span class="n">corner</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
                    <span class="k">return</span> <span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">corner</span><span class="p">)</span>
        <span class="k">return</span> <span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="bp">None</span><span class="p">)</span>
       
<div class="viewcode-block" id="Fatgraph.compute_boundary_cycles"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.compute_boundary_cycles">[docs]</a>    <span class="k">def</span> <span class="nf">compute_boundary_cycles</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return a list of boundary cycles of this `Fatgraph` object.</span>

<span class="sd">        Boundary cycles are represented as a cyclic list of &#39;corners&#39;:</span>
<span class="sd">        a corner is a triple `(v, i, j)` consisting of a vertex and</span>
<span class="sd">        two consecutive indices (in the cyclic order, so, either `j ==</span>
<span class="sd">        i+1` or `i` and `j` are the starting and ending indices)::</span>
<span class="sd">        </span>
<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2,1,0]),Vertex([2,0,1])]).compute_boundary_cycles()</span>
<span class="sd">          [BoundaryCycle([(1, 2, 0), (0, 0, 1)]),</span>
<span class="sd">           BoundaryCycle([(0, 1, 2), (1, 1, 2)]),</span>
<span class="sd">           BoundaryCycle([(0, 2, 0), (1, 0, 1)])]</span>

<span class="sd">        This verbose representation allows one to distinguish the</span>
<span class="sd">        boundary cycles made from the same set of edges::</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([0,1,2,0,1,2])]).compute_boundary_cycles()</span>
<span class="sd">          [BoundaryCycle([(0, 2, 3), (0, 4, 5), (0, 0, 1)]),</span>
<span class="sd">           BoundaryCycle([(0, 1, 2), (0, 3, 4), (0, 5, 0)])]</span>
<span class="sd">        &quot;&quot;&quot;</span>
        
        <span class="c"># Build the collection of &quot;corners&quot; of `graph`,</span>
        <span class="c"># structured just like the set of vertices.</span>
        <span class="c"># By construction, `corners[v][i]` has the the</span>
        <span class="c"># form `(v,i,j)` where `j` is the index following</span>
        <span class="c"># `i` in the cyclic order.</span>
        <span class="n">corners</span> <span class="o">=</span> <span class="p">[</span> <span class="p">[</span> <span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">%</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v</span><span class="p">]))</span>
                      <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v</span><span class="p">]))</span> <span class="p">]</span>
                    <span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">)</span> <span class="p">]</span>

        <span class="n">result</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
            <span class="c"># fast-forward to the first unused corner</span>
            <span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">corner</span><span class="p">)</span> <span class="o">=</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_first_unused_corner</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">,</span> <span class="n">corners</span><span class="p">)</span>
            <span class="k">if</span> <span class="n">corner</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
                <span class="k">break</span>

            <span class="c"># build a list of corners comprising the same boundary</span>
            <span class="c"># cycle: start with one corner, follow the edge starting</span>
            <span class="c"># at the second delimiter of the corner to its other</span>
            <span class="c"># endpoint, and repeat until we come back to the starting</span>
            <span class="c"># point.  </span>
            <span class="n">start</span> <span class="o">=</span> <span class="p">(</span><span class="n">v</span><span class="p">,</span><span class="n">i</span><span class="p">)</span>
            <span class="n">triples</span> <span class="o">=</span> <span class="p">[]</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">v</span><span class="p">,</span><span class="n">i</span><span class="p">)</span> <span class="o">!=</span> <span class="n">start</span> <span class="ow">or</span> <span class="nb">len</span><span class="p">(</span><span class="n">triples</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
                <span class="k">assert</span> <span class="n">corners</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span>
                <span class="n">corner</span> <span class="o">=</span> <span class="n">corners</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">i</span><span class="p">]</span>
                <span class="n">corners</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="bp">None</span>
                <span class="n">triples</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">corner</span><span class="p">)</span>
                <span class="k">assert</span> <span class="n">v</span> <span class="o">==</span> <span class="n">corner</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
                <span class="k">assert</span> <span class="n">i</span> <span class="o">==</span> <span class="n">corner</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
                <span class="n">j</span> <span class="o">=</span> <span class="n">corner</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span>
                <span class="n">edgeno</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">j</span><span class="p">]</span>
                <span class="p">(</span><span class="n">v</span><span class="p">,</span><span class="n">i</span><span class="p">)</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">edgeno</span><span class="p">]</span><span class="o">.</span><span class="n">other_end</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">j</span><span class="p">)</span>
            <span class="n">result</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">BoundaryCycle</span><span class="p">(</span><span class="n">triples</span><span class="p">))</span>

        <span class="k">return</span> <span class="n">result</span>
        
</div>
<div class="viewcode-block" id="Fatgraph.bridge"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.bridge">[docs]</a>    <span class="k">def</span> <span class="nf">bridge</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">edge1</span><span class="p">,</span> <span class="n">side1</span><span class="p">,</span> <span class="n">edge2</span><span class="p">,</span> <span class="n">side2</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return a new `Fatgraph`, formed by inserting trivalent</span>
<span class="sd">        vertices in the middle of edges `edge1` and `edge2` and</span>
<span class="sd">        connecting them with a new edge.</span>

<span class="sd">          &gt;&gt;&gt; g = Fatgraph([Vertex([0,1,2]), Vertex([0,2,1])])</span>
<span class="sd">          &gt;&gt;&gt; g1 = g.bridge(0, 0, 1, 1)</span>
<span class="sd">          &gt;&gt;&gt; g1 is g</span>
<span class="sd">          False</span>
<span class="sd">          &gt;&gt;&gt; g1 == g</span>
<span class="sd">          False</span>
<span class="sd">          </span>
<span class="sd">        Arguments `side1` and `side2` control which side the new edge</span>
<span class="sd">        is attached to (valid values are 0 or 1), i.e., which of the</span>
<span class="sd">        two inequivalent cyclic orders the new trivalent vertices will</span>
<span class="sd">        be given::</span>
<span class="sd">        </span>
<span class="sd">          &gt;&gt;&gt; g = Fatgraph([Vertex([0,1,2]), Vertex([0,2,1])])</span>
<span class="sd">          &gt;&gt;&gt; g1 = g.bridge(0, 0, 1, 0)</span>
<span class="sd">          &gt;&gt;&gt; g2 = g.bridge(0, 1, 1, 0)</span>
<span class="sd">          &gt;&gt;&gt; g1 == g2</span>
<span class="sd">          False</span>

<span class="sd">        In more detail: let 0,1,2 be the indices of the edges attached</span>
<span class="sd">        to the new vertex in the middle of `edge1`, where 0,1 denote</span>
<span class="sd">        the two halves of `edge1`.  If `side1` is `0`, then the new</span>
<span class="sd">        trivalent vertex will have the cyclic order [0,1,2]; if</span>
<span class="sd">        `side1` is `1`, then 0,1 are swapped and the new trivalent</span>
<span class="sd">        vertex gets the cyclic order [1,0,2]::</span>

<span class="sd">          &gt;&gt;&gt; g1 == Fatgraph([Vertex([0,1,2]), Vertex([4,2,5]), Vertex([0,4,3]), Vertex([1,5,3])])</span>
<span class="sd">          True</span>
<span class="sd">          &gt;&gt;&gt; g2 == Fatgraph([Vertex([0,1,2]), Vertex([4,2,5]), Vertex([4,0,3]), Vertex([1,5,3])])</span>
<span class="sd">          True</span>

<span class="sd">        It is worth noting that this procedure involves 5 edges in</span>
<span class="sd">        total, 3 of which need new indices.</span>

<span class="sd">          &gt;&gt;&gt; g.num_edges</span>
<span class="sd">          3</span>
<span class="sd">          &gt;&gt;&gt; g1.num_edges</span>
<span class="sd">          6</span>
<span class="sd">          </span>
<span class="sd">        This function is obviously symmetric: the pairs `edge1, side1`</span>
<span class="sd">        and `edge2, side2` can be swapped and the result stays the</span>
<span class="sd">        same::</span>

<span class="sd">          &gt;&gt;&gt; g3 = g.bridge(1, 0, 0, 0)</span>
<span class="sd">          &gt;&gt;&gt; g1 == g3</span>
<span class="sd">          True</span>

<span class="sd">          &gt;&gt;&gt; g4 = g.bridge(1, 0, 0, 1)</span>
<span class="sd">          &gt;&gt;&gt; g2 == g4</span>
<span class="sd">          True</span>

<span class="sd">        Examples::</span>
<span class="sd">        </span>
<span class="sd">        1) Bridging different sides of the same edge may yield</span>
<span class="sd">        different results::</span>
<span class="sd">        </span>
<span class="sd">          &gt;&gt;&gt; g.bridge(0, 0, 1, 0)  == Fatgraph([Vertex([0,1,2]), Vertex([4,2,5]), Vertex([0,4,3]), Vertex([1,5,3])])</span>
<span class="sd">          True</span>
<span class="sd">          </span>
<span class="sd">          &gt;&gt;&gt; g.bridge(0, 1, 1, 0) == Fatgraph([Vertex([0,1,2]), Vertex([4,2,5]), Vertex([4,0,3]), Vertex([1,5,3])])</span>
<span class="sd">          True</span>

<span class="sd">        2) One can connect an edge to itself on different sides::</span>
<span class="sd">        </span>
<span class="sd">          &gt;&gt;&gt; g.bridge(0, 0, 0, 1) == Fatgraph([Vertex([0,1,2]), Vertex([5,2,1]), Vertex([0,4,3]), Vertex([5,4,3])])</span>
<span class="sd">          True</span>

<span class="sd">        3) And also with both ends on the same side::</span>
<span class="sd">        </span>
<span class="sd">          &gt;&gt;&gt; g.bridge(0, 0, 0, 0) == Fatgraph([Vertex([0,1,2]), Vertex([5,2,1]), Vertex([0,4,3]), Vertex([4,5,3])])</span>
<span class="sd">          True</span>
<span class="sd">          </span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="n">side1</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">],</span> \
               <span class="s">&quot;Fatgraph.bridge: Invalid value for `side1`: &#39;</span><span class="si">%s</span><span class="s">&#39; - should be 0 or 1&quot;</span> <span class="o">%</span> <span class="n">side1</span>
        <span class="k">assert</span> <span class="n">side2</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">],</span> \
               <span class="s">&quot;Fatgraph.bridge: Invalid value for `side2`: &#39;</span><span class="si">%s</span><span class="s">&#39; - should be 0 or 1&quot;</span> <span class="o">%</span> <span class="n">side2</span>
        
        <span class="n">opposite_side1</span> <span class="o">=</span> <span class="mi">0</span> <span class="k">if</span> <span class="n">side1</span><span class="o">==</span><span class="mi">1</span> <span class="k">else</span> <span class="mi">1</span>
        <span class="n">opposite_side2</span> <span class="o">=</span> <span class="mi">0</span> <span class="k">if</span> <span class="n">side2</span><span class="o">==</span><span class="mi">1</span> <span class="k">else</span> <span class="mi">1</span>

        <span class="c">## assign edge indices</span>
        <span class="n">connecting_edge</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span>
        <span class="c">## break `edge1` in two halves: if `v1a` and `v1b` are the</span>
        <span class="c">## endpoints of `edge1`, then the &quot;one_half&quot; edge extends from</span>
        <span class="c">## the `v1a` endpoint of `edge1` to the new vertex</span>
        <span class="c">## `midpoint1`; the &quot;other_half&quot; edge extends from the</span>
        <span class="c">## `midpoint1` new vertex to `v1b`.</span>
        <span class="n">one_half1</span> <span class="o">=</span> <span class="n">edge1</span>
        <span class="n">other_half1</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">+</span> <span class="mi">1</span>
        <span class="c">## break `edge2` in two halves; if `edge2` is the same edge as</span>
        <span class="c">## `edge1`, then we are breaking the second half of `edge1` in</span>
        <span class="c">## two parts.  Otherwise, proceed as above.  In any case, the</span>
        <span class="c">## &quot;other half&quot; of `edge2` needs a new edge index.</span>
        <span class="k">if</span> <span class="n">edge2</span> <span class="o">==</span> <span class="n">edge1</span><span class="p">:</span>
            <span class="n">one_half2</span> <span class="o">=</span> <span class="n">other_half1</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">one_half2</span> <span class="o">=</span> <span class="n">edge2</span>
        <span class="n">other_half2</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">+</span> <span class="mi">2</span>

        <span class="c">## assign new vertex indices</span>
        <span class="n">midpoint1_index</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span>
        <span class="n">midpoint2_index</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span> <span class="o">+</span> <span class="mi">1</span>

        <span class="k">if</span> <span class="n">side1</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
            <span class="n">midpoint1</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">other_half1</span><span class="p">,</span> <span class="n">one_half1</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>
        <span class="k">else</span><span class="p">:</span> <span class="c"># side2 == 0</span>
            <span class="n">midpoint1</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">one_half1</span><span class="p">,</span> <span class="n">other_half1</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>

        <span class="k">if</span> <span class="n">side2</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
            <span class="n">midpoint2</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">other_half2</span><span class="p">,</span> <span class="n">one_half2</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>
        <span class="k">else</span><span class="p">:</span> <span class="c"># side2 == 0</span>
            <span class="n">midpoint2</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">one_half2</span><span class="p">,</span> <span class="n">other_half2</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>

        <span class="c">## two new vertices are added: the mid-points of the connected edges.</span>
        <span class="n">new_vertices</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span> <span class="o">+</span> <span class="p">[</span><span class="n">midpoint1</span><span class="p">,</span> <span class="n">midpoint2</span><span class="p">]</span>

        <span class="c">## three new edges are added (constructed below)</span>
        <span class="n">new_edges</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span> <span class="o">+</span> <span class="p">[</span>
            <span class="bp">None</span><span class="p">,</span> <span class="c"># new edge: connecting_edge</span>
            <span class="bp">None</span><span class="p">,</span> <span class="c"># new edge: other_half1</span>
            <span class="bp">None</span><span class="p">,</span> <span class="c"># new edge: other_half2</span>
            <span class="p">]</span>
        
        <span class="c">## the connecting edge has endpoints in the mid-points of</span>
        <span class="c">## `edge1` and `edge2`, and is *always* in third position.</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">connecting_edge</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">midpoint1_index</span><span class="p">,</span> <span class="mi">2</span><span class="p">),</span> <span class="p">(</span><span class="n">midpoint2_index</span><span class="p">,</span> <span class="mi">2</span><span class="p">))</span>

        <span class="p">((</span><span class="n">v1a</span><span class="p">,</span> <span class="n">pos1a</span><span class="p">),</span> <span class="p">(</span><span class="n">v1b</span><span class="p">,</span> <span class="n">pos1b</span><span class="p">))</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">edge1</span><span class="p">]</span><span class="o">.</span><span class="n">endpoints</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">one_half1</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">v1a</span><span class="p">,</span> <span class="n">pos1a</span><span class="p">),</span> <span class="p">(</span><span class="n">midpoint1_index</span><span class="p">,</span> <span class="n">side1</span><span class="p">))</span>
        <span class="k">if</span> <span class="n">edge1</span> <span class="o">!=</span> <span class="n">edge2</span><span class="p">:</span>
            <span class="c"># replace `edge1` with new `other_half1` in the second endpoint</span>
            <span class="n">new_vertices</span><span class="p">[</span><span class="n">v1b</span><span class="p">]</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">[</span><span class="n">v1b</span><span class="p">][:</span><span class="n">pos1b</span><span class="p">]</span>
                                                 <span class="o">+</span> <span class="p">[</span><span class="n">other_half1</span><span class="p">]</span>
                                                 <span class="o">+</span> <span class="n">new_vertices</span><span class="p">[</span><span class="n">v1b</span><span class="p">][</span><span class="n">pos1b</span><span class="o">+</span><span class="mi">1</span><span class="p">:])</span>
            <span class="n">new_edges</span><span class="p">[</span><span class="n">other_half1</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">midpoint1_index</span><span class="p">,</span> <span class="n">opposite_side1</span><span class="p">),</span> <span class="p">(</span><span class="n">v1b</span><span class="p">,</span> <span class="n">pos1b</span><span class="p">))</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="c"># same edge, &quot;other half&quot; ends at the second endpoint</span>
            <span class="n">new_edges</span><span class="p">[</span><span class="n">other_half1</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">midpoint1_index</span><span class="p">,</span> <span class="n">opposite_side1</span><span class="p">),</span> <span class="p">(</span><span class="n">midpoint2_index</span><span class="p">,</span> <span class="n">side2</span><span class="p">))</span>

        <span class="c"># replace `edge2` with new `other_half2` in the second</span>
        <span class="c"># endpoint; again we need to distinguish the special case when</span>
        <span class="c"># `edge1` and `edge2` are the same edge.</span>
        <span class="p">((</span><span class="n">v2a</span><span class="p">,</span> <span class="n">pos2a</span><span class="p">),</span> <span class="p">(</span><span class="n">v2b</span><span class="p">,</span> <span class="n">pos2b</span><span class="p">))</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">edge2</span><span class="p">]</span><span class="o">.</span><span class="n">endpoints</span>
        <span class="k">if</span> <span class="n">edge1</span> <span class="o">!=</span> <span class="n">edge2</span><span class="p">:</span>
            <span class="n">new_edges</span><span class="p">[</span><span class="n">one_half2</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">v2a</span><span class="p">,</span> <span class="n">pos2a</span><span class="p">),</span> <span class="p">(</span><span class="n">midpoint2_index</span><span class="p">,</span> <span class="n">side2</span><span class="p">))</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="c"># `edge1 == edge2`, so `one_half2 == other_half1`</span>
            <span class="k">pass</span> <span class="c"># new_edges[one_half2] = new_edges[other_half1]</span>
        <span class="c"># &quot;other half&quot; of second edge *always* ends at the previous</span>
        <span class="c"># edge endpoint, so replace `edge2` in `v2b`.</span>
        <span class="n">new_vertices</span><span class="p">[</span><span class="n">v2b</span><span class="p">]</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">[</span><span class="n">v2b</span><span class="p">][:</span><span class="n">pos2b</span><span class="p">]</span>
                                             <span class="o">+</span> <span class="p">[</span><span class="n">other_half2</span><span class="p">]</span>
                                             <span class="o">+</span> <span class="n">new_vertices</span><span class="p">[</span><span class="n">v2b</span><span class="p">][</span><span class="n">pos2b</span><span class="o">+</span><span class="mi">1</span><span class="p">:])</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">other_half2</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">midpoint2_index</span><span class="p">,</span> <span class="n">opposite_side2</span><span class="p">),</span> <span class="p">(</span><span class="n">v2b</span><span class="p">,</span> <span class="n">pos2b</span><span class="p">))</span>

        <span class="c">## inherit orientation, and add the three new edges in the order they were created</span>
        <span class="n">new_edge_numbering</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edge_numbering</span> <span class="o">+</span> \
                             <span class="p">[</span><span class="n">connecting_edge</span><span class="p">,</span> <span class="n">other_half1</span><span class="p">,</span> <span class="n">other_half2</span><span class="p">]</span>

        <span class="c"># build new graph </span>
        <span class="k">return</span> <span class="n">Fatgraph</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">,</span>
                        <span class="n">edges</span> <span class="o">=</span> <span class="n">new_edges</span><span class="p">,</span>
                        <span class="n">num_edges</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">+</span> <span class="mi">3</span><span class="p">,</span>
                        <span class="n">orientation</span> <span class="o">=</span> <span class="n">new_edge_numbering</span><span class="p">,</span>
                        <span class="p">)</span>
    
    </div>
<div class="viewcode-block" id="Fatgraph.bridge2"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.bridge2">[docs]</a>    <span class="k">def</span> <span class="nf">bridge2</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">edge1</span><span class="p">,</span> <span class="n">side1</span><span class="p">,</span> <span class="n">other</span><span class="p">,</span> <span class="n">edge2</span><span class="p">,</span> <span class="n">side2</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return a new `Fatgraph`, formed by connecting the midpoints</span>
<span class="sd">        of `edge1` on `self` and `edge2` on `other`.</span>
<span class="sd">        </span>
<span class="sd">          &gt;&gt;&gt; g1 = Fatgraph([Vertex([0,1,2]), Vertex([0,2,1])])</span>
<span class="sd">          &gt;&gt;&gt; g2 = Fatgraph([Vertex([0,1,2,0,1,2])])</span>
<span class="sd">          &gt;&gt;&gt; g = Fatgraph.bridge2(g1, 0, 0, g2, 1, 1)</span>
<span class="sd">          &gt;&gt;&gt; g is g1</span>
<span class="sd">          False</span>
<span class="sd">          &gt;&gt;&gt; g is g2</span>
<span class="sd">          False</span>
<span class="sd">          &gt;&gt;&gt; g == Fatgraph([Vertex([0,1,2]), Vertex([6,2,1]), Vertex([3,4,5,3,7,5]), Vertex([0,6,8]), Vertex([4,7,8])])</span>
<span class="sd">          True</span>
<span class="sd">          </span>
<span class="sd">        New trivalent vertices are inserted in the middle of the</span>
<span class="sd">        connected edges.  Arguments `side1` and `side2` control which</span>
<span class="sd">        side the new edge is attached to (valid values are 0 or 1),</span>
<span class="sd">        i.e., which of the two inequivalent cyclic orders the new</span>
<span class="sd">        trivalent vertices will be given (see `Fatgraph.bridge()`).</span>
<span class="sd">        </span>
<span class="sd">        It is worth noting that this procedure adds 3 edges and 2</span>
<span class="sd">        vertices to the edge total of `self` and `other`::</span>
<span class="sd">        </span>
<span class="sd">          &gt;&gt;&gt; g.num_edges == g1.num_edges + g2.num_edges + 3</span>
<span class="sd">          True</span>
<span class="sd">          &gt;&gt;&gt; g.num_vertices == g1.num_vertices + g2.num_vertices + 2</span>
<span class="sd">          True</span>
<span class="sd">          </span>
<span class="sd">        This function is obviously symmetric: the triplets `self, edge1, side1`</span>
<span class="sd">        and `other, edge2, side2` can be swapped and the result stays the</span>
<span class="sd">        same (up to isomorphisms)::</span>

<span class="sd">          &gt;&gt;&gt; g_ = Fatgraph.bridge2(g2, 1, 1, g1, 0, 0)</span>
<span class="sd">          &gt;&gt;&gt; g == g_</span>
<span class="sd">          True</span>

<span class="sd">        *Caveat:* If `self == other` then the resulting graph is made</span>
<span class="sd">        up of *two copies* of `self` with a new edge connecting</span>
<span class="sd">        `edge1` on one copy and `edge2` on the other.</span>
<span class="sd">         </span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="n">side1</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">],</span> \
               <span class="s">&quot;Fatgraph.bridge2: Invalid value for `side1`: &#39;</span><span class="si">%s</span><span class="s">&#39; -- should be 0 or 1&quot;</span> <span class="o">%</span> <span class="n">side1</span>
        <span class="k">assert</span> <span class="n">side2</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">],</span> \
               <span class="s">&quot;Fatgraph.bridge2: Invalid value for `side2`: &#39;</span><span class="si">%s</span><span class="s">&#39; -- should be 0 or 1&quot;</span> <span class="o">%</span> <span class="n">side2</span>

        <span class="c">## First, build a (non-connected) graph from the disjoint</span>
        <span class="c">## union of `self` and `other`.</span>

        <span class="c"># Edges of `other` are renumbered depending on whether</span>
        <span class="c"># they are internal of external edges:</span>
        <span class="c">#   - internal edges in `other` have numbers ranging from 0 to</span>
        <span class="c">#     `other.num_edges`: they get new numbers starting from</span>
        <span class="c">#     `self.num_edges` and counting upwards</span>
        <span class="n">renumber_other_edges</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">((</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="o">+</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span>
                                    <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="n">other</span><span class="o">.</span><span class="n">num_edges</span><span class="p">))</span>
        <span class="c"># Orientation needs the same numbering:</span>
        <span class="n">new_edge_numbering</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edge_numbering</span> \
                             <span class="o">+</span> <span class="n">ltranslate</span><span class="p">(</span><span class="n">renumber_other_edges</span><span class="p">,</span> <span class="n">other</span><span class="o">.</span><span class="n">edge_numbering</span><span class="p">)</span>
        <span class="c"># Similarly, vertices of `self` retain indices `[0..v]`, while</span>
        <span class="c"># vertices of `other` follow.</span>
        <span class="n">new_vertices</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span> \
                       <span class="o">+</span> <span class="p">[</span> <span class="n">Vertex</span><span class="p">(</span><span class="n">ltranslate</span><span class="p">(</span><span class="n">renumber_other_edges</span><span class="p">,</span> <span class="n">ov</span><span class="p">))</span>
                           <span class="k">for</span> <span class="n">ov</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">vertices</span> <span class="p">]</span>
        <span class="n">renumber_other_vertices</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">((</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="o">+</span><span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">)</span>
                                       <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="n">other</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">))</span>
        <span class="c"># build new edges: vertex indices need to be shifted for</span>
        <span class="c"># endpoints, but attachment indices are the same; three new</span>
        <span class="c"># edges are added at the tail of the list</span>
        <span class="n">new_edges</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span> \
                    <span class="o">+</span> <span class="p">[</span> <span class="n">Edge</span><span class="p">((</span><span class="n">renumber_other_vertices</span><span class="p">[</span><span class="n">x</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]],</span> <span class="n">x</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">1</span><span class="p">]),</span>
                             <span class="p">(</span><span class="n">renumber_other_vertices</span><span class="p">[</span><span class="n">x</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">]],</span> <span class="n">x</span><span class="o">.</span><span class="n">endpoints</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="mi">1</span><span class="p">]))</span>
                        <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">edges</span> <span class="p">]</span> \
                    <span class="o">+</span> <span class="p">[</span><span class="bp">None</span><span class="p">,</span> <span class="c"># connecting_edge</span>
                       <span class="bp">None</span><span class="p">,</span> <span class="c"># other_half1</span>
                       <span class="bp">None</span><span class="p">]</span> <span class="c"># other_half2</span>

        <span class="n">edge2</span> <span class="o">=</span> <span class="n">renumber_other_edges</span><span class="p">[</span><span class="n">edge2</span><span class="p">]</span> <span class="c"># index changed in `new_edges`</span>
        
        <span class="n">opposite_side1</span> <span class="o">=</span> <span class="mi">0</span> <span class="k">if</span> <span class="n">side1</span> <span class="k">else</span> <span class="mi">1</span>
        <span class="n">opposite_side2</span> <span class="o">=</span> <span class="mi">0</span> <span class="k">if</span> <span class="n">side2</span> <span class="k">else</span> <span class="mi">1</span>

        <span class="c">## assign edge indices</span>
        <span class="n">connecting_edge</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">+</span> <span class="n">other</span><span class="o">.</span><span class="n">num_edges</span>
        <span class="c">## break `edge1` in two halves: if `v1a` and `v1b` are the</span>
        <span class="c">## endpoints of `edge1`, then the &quot;one_half&quot; edge extends from</span>
         <span class="c">## the `v1a` endpoint of `edge1` to the new vertex</span>
        <span class="c">## `midpoint1`; the &quot;other_half&quot; edge extends from the</span>
        <span class="c">## `midpoint1` new vertex to `v1b`.</span>
        <span class="n">one_half1</span> <span class="o">=</span> <span class="n">edge1</span>
        <span class="n">other_half1</span> <span class="o">=</span> <span class="n">connecting_edge</span> <span class="o">+</span> <span class="mi">1</span>
        <span class="c">## break `edge2` in two halves; same as above.</span>
        <span class="n">one_half2</span> <span class="o">=</span> <span class="n">edge2</span>
        <span class="n">other_half2</span> <span class="o">=</span> <span class="n">connecting_edge</span> <span class="o">+</span> <span class="mi">2</span>

        <span class="c">## assign new vertex indices</span>
        <span class="n">midpoint1_index</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">)</span>
        <span class="n">midpoint2_index</span> <span class="o">=</span> <span class="n">midpoint1_index</span> <span class="o">+</span> <span class="mi">1</span>

        <span class="k">if</span> <span class="n">side1</span><span class="p">:</span>
            <span class="n">midpoint1</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">other_half1</span><span class="p">,</span> <span class="n">one_half1</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">midpoint1</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">one_half1</span><span class="p">,</span> <span class="n">other_half1</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>

        <span class="k">if</span> <span class="n">side2</span><span class="p">:</span>
            <span class="n">midpoint2</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">other_half2</span><span class="p">,</span> <span class="n">one_half2</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">midpoint2</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">one_half2</span><span class="p">,</span> <span class="n">other_half2</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>

        <span class="c">## two new vertices are added: the mid-points of the connected edges.</span>
        <span class="n">new_vertices</span> <span class="o">+=</span> <span class="p">[</span><span class="n">midpoint1</span><span class="p">,</span> <span class="n">midpoint2</span><span class="p">]</span>
        <span class="c">## the connecting edge has endpoints in the mid-points of</span>
        <span class="c">## `edge1` and `edge2`, and is *always* in third position.</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">connecting_edge</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">midpoint1_index</span><span class="p">,</span> <span class="mi">2</span><span class="p">),</span> <span class="p">(</span><span class="n">midpoint2_index</span><span class="p">,</span> <span class="mi">2</span><span class="p">))</span>

        <span class="p">((</span><span class="n">v1a</span><span class="p">,</span> <span class="n">pos1a</span><span class="p">),</span> <span class="p">(</span><span class="n">v1b</span><span class="p">,</span> <span class="n">pos1b</span><span class="p">))</span> <span class="o">=</span> <span class="n">new_edges</span><span class="p">[</span><span class="n">edge1</span><span class="p">]</span><span class="o">.</span><span class="n">endpoints</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">one_half1</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">v1a</span><span class="p">,</span> <span class="n">pos1a</span><span class="p">),</span> <span class="p">(</span><span class="n">midpoint1_index</span><span class="p">,</span> <span class="n">side1</span><span class="p">))</span>
        <span class="c"># replace `edge1` with new `other_half1` in the second endpoint</span>
        <span class="n">new_vertices</span><span class="p">[</span><span class="n">v1b</span><span class="p">]</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">[</span><span class="n">v1b</span><span class="p">][:</span><span class="n">pos1b</span><span class="p">]</span>
                                             <span class="o">+</span> <span class="p">[</span><span class="n">other_half1</span><span class="p">]</span>
                                             <span class="o">+</span> <span class="n">new_vertices</span><span class="p">[</span><span class="n">v1b</span><span class="p">][</span><span class="n">pos1b</span><span class="o">+</span><span class="mi">1</span><span class="p">:])</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">other_half1</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">midpoint1_index</span><span class="p">,</span> <span class="n">opposite_side1</span><span class="p">),</span> <span class="p">(</span><span class="n">v1b</span><span class="p">,</span> <span class="n">pos1b</span><span class="p">))</span>

        <span class="c"># replace `edge2` with new `other_half2` in the second</span>
        <span class="c"># endpoint; again we need to distinguish the special case when</span>
        <span class="c"># `edge1` and `edge2` are the same edge.</span>
        <span class="p">((</span><span class="n">v2a</span><span class="p">,</span> <span class="n">pos2a</span><span class="p">),</span> <span class="p">(</span><span class="n">v2b</span><span class="p">,</span> <span class="n">pos2b</span><span class="p">))</span> <span class="o">=</span> <span class="n">new_edges</span><span class="p">[</span><span class="n">edge2</span><span class="p">]</span><span class="o">.</span><span class="n">endpoints</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">one_half2</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">v2a</span><span class="p">,</span> <span class="n">pos2a</span><span class="p">),</span> <span class="p">(</span><span class="n">midpoint2_index</span><span class="p">,</span> <span class="n">side2</span><span class="p">))</span>
        <span class="c"># &quot;other half&quot; of second edge *always* ends at the previous</span>
        <span class="c"># edge endpoint, so replace `edge2` in `v2b`.</span>
        <span class="n">new_vertices</span><span class="p">[</span><span class="n">v2b</span><span class="p">]</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">[</span><span class="n">v2b</span><span class="p">][:</span><span class="n">pos2b</span><span class="p">]</span>
                                             <span class="o">+</span> <span class="p">[</span><span class="n">other_half2</span><span class="p">]</span>
                                             <span class="o">+</span> <span class="n">new_vertices</span><span class="p">[</span><span class="n">v2b</span><span class="p">][</span><span class="n">pos2b</span><span class="o">+</span><span class="mi">1</span><span class="p">:])</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">other_half2</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">midpoint2_index</span><span class="p">,</span> <span class="n">opposite_side2</span><span class="p">),</span> <span class="p">(</span><span class="n">v2b</span><span class="p">,</span> <span class="n">pos2b</span><span class="p">))</span>

        <span class="c">## inherit orientation, and add the three new edges in the order they were created</span>
        <span class="n">new_edge_numbering</span> <span class="o">+=</span>  <span class="p">[</span><span class="n">connecting_edge</span><span class="p">,</span> <span class="n">other_half1</span><span class="p">,</span> <span class="n">other_half2</span><span class="p">]</span>

        <span class="c"># build new graph </span>
        <span class="k">return</span> <span class="n">Fatgraph</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">,</span>
                        <span class="n">edges</span> <span class="o">=</span> <span class="n">new_edges</span><span class="p">,</span>
                        <span class="n">num_edges</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">+</span> <span class="n">other</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">+</span> <span class="mi">3</span><span class="p">,</span>
                        <span class="n">orientation</span> <span class="o">=</span> <span class="n">new_edge_numbering</span><span class="p">,</span>
                        <span class="p">)</span>

</div>
    <span class="nd">@ocache_contract</span>
<div class="viewcode-block" id="Fatgraph.contract"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.contract">[docs]</a>    <span class="k">def</span> <span class="nf">contract</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">edge</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return new `Fatgraph` obtained by contracting the specified edge.</span>

<span class="sd">        Examples::</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2,2,0]), Vertex([0,1,1])]).contract(0)</span>
<span class="sd">          Fatgraph([Vertex([1, 1, 0, 0])])</span>
<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2,1,0]), Vertex([2,0,1])]).contract(1)</span>
<span class="sd">          Fatgraph([Vertex([0, 1, 1, 0])])</span>

<span class="sd">        The M_{1,1} trivalent graph yield the same result no matter</span>
<span class="sd">        what edge is contracted::</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2,1,0]), Vertex([2,1,0])]).contract(0)</span>
<span class="sd">          Fatgraph([Vertex([1, 0, 1, 0])])</span>
<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2,1,0]), Vertex([2,1,0])]).contract(1)</span>
<span class="sd">          Fatgraph([Vertex([0, 1, 0, 1])])</span>
<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2,1,0]), Vertex([2,1,0])]).contract(2)</span>
<span class="sd">          Fatgraph([Vertex([1, 0, 1, 0])])</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="ow">not</span> <span class="bp">self</span><span class="o">.</span><span class="n">is_loop</span><span class="p">(</span><span class="n">edge</span><span class="p">),</span> \
               <span class="s">&quot;Fatgraph.contract: cannot contract a loop.&quot;</span>
        <span class="k">assert</span> <span class="p">(</span><span class="n">edge</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">)</span> <span class="ow">and</span> <span class="p">(</span><span class="n">edge</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">),</span> \
               <span class="s">&quot;Fatgraph.contract: invalid edge number (</span><span class="si">%d</span><span class="s">):&quot;</span>\
               <span class="s">&quot; must be in range 0..</span><span class="si">%d</span><span class="s">&quot;</span> \
               <span class="o">%</span> <span class="p">(</span><span class="n">edge</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span>

        <span class="c">## Plug the higher-numbered vertex into the lower-numbered one.</span>
        
        <span class="c"># store endpoints of the edge-to-be-contracted</span>
        <span class="p">((</span><span class="n">v1</span><span class="p">,</span> <span class="n">pos1</span><span class="p">),</span> <span class="p">(</span><span class="n">v2</span><span class="p">,</span> <span class="n">pos2</span><span class="p">))</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">edge</span><span class="p">]</span><span class="o">.</span><span class="n">endpoints</span>
        <span class="k">assert</span> <span class="n">v1</span> <span class="o">&lt;</span> <span class="n">v2</span>

        <span class="c"># Build new list of vertices, removing the contracted edge and</span>
        <span class="c"># shifting all indices above:</span>
        <span class="c">#   - edges numbered 0..edge-1 are unchanged;</span>
        <span class="c">#   - edges numbered `edge+1`.. are renumbered, </span>
        <span class="c">#     shifting the number down one position;</span>
        <span class="c">#   - edge `edge` is kept intact, will be removed by mating</span>
        <span class="c">#     operation (see below).</span>
        <span class="n">renumber_edges</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">((</span><span class="n">i</span><span class="p">,</span><span class="n">i</span><span class="p">)</span>
                              <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">edge</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span>
        <span class="n">renumber_edges</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="nb">dict</span><span class="p">((</span><span class="n">i</span><span class="p">,</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>
                              <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="n">edge</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)))</span>
        <span class="c"># See `itranslate` in utils.py for how this prescription is</span>
        <span class="c"># encoded in the `renumber_edges` mapping.</span>
        <span class="n">new_vertices</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Vertex</span><span class="p">([</span> <span class="n">renumber_edges</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="k">for</span> <span class="n">e</span> <span class="ow">in</span> <span class="n">V</span> <span class="p">])</span>
                         <span class="k">for</span> <span class="n">V</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span> <span class="p">]</span>

        <span class="c"># Mate endpoints of contracted edge:</span>
        <span class="c"># 1. Rotate endpoints `v1`, `v2` so that the given edge would</span>
        <span class="c">#    appear *last* in `v1` and *first* in `v2` (*Note:* since</span>
        <span class="c">#    `v1`, `v2` are *cyclic*, this means that we do the same</span>
        <span class="c">#    operation on `v1` and `v2` alike).</span>
        <span class="c"># 2. Join vertices by concatenating the list of incident</span>
        <span class="c">#    edges;</span>
        <span class="c"># 3. Set new `i1` vertex in place of old first endpoint:</span>
        <span class="n">new_vertices</span><span class="p">[</span><span class="n">v1</span><span class="p">]</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">(</span>
            <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_rotate_and_trim</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">[</span><span class="n">v1</span><span class="p">],</span> <span class="n">pos1</span><span class="p">)</span>
            <span class="o">+</span>
            <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_rotate_and_trim</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">[</span><span class="n">v2</span><span class="p">],</span> <span class="n">pos2</span><span class="p">)</span>
            <span class="p">)</span>
        <span class="c"># 4. Remove second endpoint from list of new vertices:</span>
        <span class="k">del</span> <span class="n">new_vertices</span><span class="p">[</span><span class="n">v2</span><span class="p">]</span>

        <span class="c">## Orientation of the contracted graph.</span>
        <span class="n">cut</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edge_numbering</span><span class="p">[</span><span class="n">edge</span><span class="p">]</span>
        <span class="c"># edges with index below the contracted one are untouched</span>
        <span class="n">renumber_edge_numbering</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">((</span><span class="n">x</span><span class="p">,</span><span class="n">x</span><span class="p">)</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="n">cut</span><span class="p">))</span>
        <span class="c"># edges with index above the contracted one are shifted down</span>
        <span class="c"># one position</span>
        <span class="n">renumber_edge_numbering</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="nb">dict</span><span class="p">((</span><span class="n">x</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">x</span><span class="p">)</span>
                                      <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="n">cut</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)))</span>
        <span class="n">new_edge_numbering</span> <span class="o">=</span> <span class="p">[</span> <span class="n">renumber_edge_numbering</span><span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">edge_numbering</span><span class="p">[</span><span class="n">x</span><span class="p">]]</span>
                               <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span>
                               <span class="k">if</span> <span class="n">x</span> <span class="o">!=</span> <span class="n">edge</span> <span class="p">]</span>
        
        <span class="c"># build new graph</span>
        <span class="k">return</span> <span class="n">Fatgraph</span><span class="p">(</span>
            <span class="n">new_vertices</span><span class="p">,</span>
            <span class="n">orientation</span> <span class="o">=</span> <span class="n">new_edge_numbering</span><span class="p">,</span>
            <span class="p">)</span>

    <span class="c">#@cython.locals(L=list, p=cython.int)</span>
    <span class="c">#@cython.cfunc(list)</span></div>
    <span class="nd">@staticmethod</span>
    <span class="k">def</span> <span class="nf">_rotate_and_trim</span><span class="p">(</span><span class="n">V</span><span class="p">,</span> <span class="n">p</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Return a copy of the given list `V`, with items rotated `p`</span>
<span class="sd">        positions leftwards; additionally, the item originally at</span>
<span class="sd">        position `p` is removed.</span>

<span class="sd">        Examples::</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph._rotate_and_trim([1,2,3,4,5], 2)</span>
<span class="sd">          [4, 5, 1, 2]</span>

<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="n">V</span><span class="p">[</span><span class="n">p</span><span class="o">+</span><span class="mi">1</span><span class="p">:]</span> <span class="o">+</span> <span class="n">V</span><span class="p">[:</span><span class="n">p</span><span class="p">]</span>


<div class="viewcode-block" id="Fatgraph.contract_boundary_cycle"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.contract_boundary_cycle">[docs]</a>    <span class="k">def</span> <span class="nf">contract_boundary_cycle</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">bcy</span><span class="p">,</span> <span class="n">vi1</span><span class="p">,</span> <span class="n">vi2</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return a new `BoundaryCycle` instance, image of `bcy` under</span>
<span class="sd">        the topological map that contracts the edge with endpoints</span>
<span class="sd">        `(v1,i1)` and `(v2,i2)` that are passed as first and second</span>
<span class="sd">        argument.</span>

<span class="sd">        XXX: return `bcy` if neither `v1` nor `v2` are contained in it.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="p">(</span><span class="n">v1</span><span class="p">,</span> <span class="n">pos1</span><span class="p">)</span> <span class="o">=</span> <span class="n">vi1</span>
        <span class="p">(</span><span class="n">v2</span><span class="p">,</span> <span class="n">pos2</span><span class="p">)</span> <span class="o">=</span> <span class="n">vi2</span>
        <span class="n">l1</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v1</span><span class="p">])</span>
        <span class="n">l2</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v2</span><span class="p">])</span>
        <span class="n">new_bcy</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="k">for</span> <span class="n">corner</span> <span class="ow">in</span> <span class="n">bcy</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">corner</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">==</span> <span class="n">v1</span><span class="p">:</span>
                <span class="k">if</span> <span class="n">pos1</span> <span class="o">==</span> <span class="n">corner</span><span class="p">[</span><span class="mi">1</span><span class="p">]:</span>
                    <span class="c"># skip this corner, keep only one of the</span>
                    <span class="c"># corners limited by the contracted edge</span>
                    <span class="k">continue</span>
                <span class="k">else</span><span class="p">:</span> 
                    <span class="n">i1</span> <span class="o">=</span> <span class="p">(</span><span class="n">corner</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">-</span> <span class="n">pos1</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="n">l1</span>
                    <span class="n">i2</span> <span class="o">=</span> <span class="p">(</span><span class="n">corner</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">-</span> <span class="n">pos1</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="n">l1</span>
                    <span class="k">assert</span> <span class="p">(</span><span class="n">i1</span><span class="o">+</span><span class="mi">1</span><span class="o">-</span><span class="n">i2</span><span class="p">)</span> <span class="o">%</span> <span class="n">l1</span> <span class="o">==</span> <span class="mi">0</span> <span class="c"># i1,i2 denote successive indices</span>
                    <span class="k">assert</span> <span class="n">i1</span> <span class="o">!=</span> <span class="n">l1</span><span class="o">-</span><span class="mi">1</span> <span class="c"># would collide with contracted corners from `v2`</span>
                    <span class="n">new_bcy</span><span class="o">.</span><span class="n">append</span><span class="p">((</span><span class="n">v1</span><span class="p">,</span> <span class="n">i1</span><span class="p">,</span> <span class="n">i2</span><span class="p">))</span>
            <span class="k">elif</span> <span class="n">corner</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">==</span> <span class="n">v2</span><span class="p">:</span>
                <span class="k">if</span> <span class="n">pos2</span> <span class="o">==</span> <span class="n">corner</span><span class="p">[</span><span class="mi">1</span><span class="p">]:</span>
                    <span class="c"># skip this corner, keep only one of the</span>
                    <span class="c"># corners limited by the contracted edge</span>
                    <span class="k">continue</span>
                <span class="k">if</span> <span class="n">pos2</span> <span class="o">==</span> <span class="n">corner</span><span class="p">[</span><span class="mi">2</span><span class="p">]:</span>
                    <span class="n">new_bcy</span><span class="o">.</span><span class="n">append</span><span class="p">((</span><span class="n">v1</span><span class="p">,</span> <span class="n">l1</span><span class="o">+</span><span class="n">l2</span><span class="o">-</span><span class="mi">3</span><span class="p">,</span> <span class="mi">0</span><span class="p">))</span>
                <span class="k">else</span><span class="p">:</span>
                    <span class="n">i1</span> <span class="o">=</span> <span class="n">l1</span><span class="o">-</span><span class="mi">1</span> <span class="o">+</span> <span class="p">((</span><span class="n">corner</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">-</span> <span class="n">pos2</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="n">l2</span><span class="p">)</span>
                    <span class="n">i2</span> <span class="o">=</span> <span class="n">l1</span><span class="o">-</span><span class="mi">1</span> <span class="o">+</span> <span class="p">((</span><span class="n">corner</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">-</span> <span class="n">pos2</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="n">l2</span><span class="p">)</span>
                    <span class="k">assert</span> <span class="p">(</span><span class="n">i1</span><span class="o">+</span><span class="mi">1</span><span class="o">-</span><span class="n">i2</span><span class="p">)</span> <span class="o">%</span> <span class="n">l1</span> <span class="o">==</span> <span class="mi">0</span> <span class="c"># i1,i2 denote successive indices</span>
                    <span class="n">new_bcy</span><span class="o">.</span><span class="n">append</span><span class="p">((</span><span class="n">v1</span><span class="p">,</span> <span class="n">i1</span><span class="p">,</span> <span class="n">i2</span><span class="p">))</span>
            <span class="k">elif</span> <span class="n">corner</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">v2</span><span class="p">:</span>
                <span class="c"># shift vertices after `v2` one position down</span>
                <span class="n">new_bcy</span><span class="o">.</span><span class="n">append</span><span class="p">((</span><span class="n">corner</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">corner</span><span class="p">[</span><span class="mi">1</span><span class="p">],</span> <span class="n">corner</span><span class="p">[</span><span class="mi">2</span><span class="p">]))</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="c"># pass corner unchanged</span>
                <span class="n">new_bcy</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">corner</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">__debug__</span><span class="p">:</span>
            <span class="n">cnt</span> <span class="o">=</span> <span class="p">{}</span>
            <span class="k">for</span> <span class="n">corner</span> <span class="ow">in</span> <span class="n">new_bcy</span><span class="p">:</span>
                <span class="k">try</span><span class="p">:</span>
                    <span class="n">cnt</span><span class="p">[</span><span class="n">corner</span><span class="p">]</span> <span class="o">+=</span> <span class="mi">1</span>
                <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
                    <span class="n">cnt</span><span class="p">[</span><span class="n">corner</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span>
            <span class="k">for</span> <span class="p">(</span><span class="n">corner</span><span class="p">,</span> <span class="n">count</span><span class="p">)</span> <span class="ow">in</span> <span class="n">cnt</span><span class="o">.</span><span class="n">iteritems</span><span class="p">():</span>
                <span class="k">assert</span> <span class="n">count</span> <span class="o">==</span> <span class="mi">1</span><span class="p">,</span> \
                       <span class="s">&quot;BoundaryCycle.contract():&quot;</span> \
                       <span class="s">&quot; Corner </span><span class="si">%s</span><span class="s"> appears </span><span class="si">%d</span><span class="s"> times in contracted boundary cycle </span><span class="si">%s</span><span class="s">&quot;</span> \
                       <span class="o">%</span> <span class="p">(</span><span class="n">corner</span><span class="p">,</span> <span class="n">count</span><span class="p">,</span> <span class="n">new_bcy</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">BoundaryCycle</span><span class="p">(</span><span class="n">new_bcy</span><span class="p">)</span>

</div>
    <span class="nd">@ocache0</span>
<div class="viewcode-block" id="Fatgraph.edge_orbits"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.edge_orbits">[docs]</a>    <span class="k">def</span> <span class="nf">edge_orbits</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Compute orbits of the edges under the action of graph</span>
<span class="sd">        automorphism group, and a representative for each orbit.</span>
<span class="sd">        </span>
<span class="sd">        Returns a dictionary, whose keys are the representatives, and</span>
<span class="sd">        whose values are the orbits.  Orbits are represented as Python</span>
<span class="sd">        `set` objects.</span>

<span class="sd">        Examples::</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([0,1,2]), Vertex([0,1,2])]).edge_orbits()</span>
<span class="sd">          {0: set([0, 1, 2])}</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([1, 0, 2]), Vertex([2, 1, 0])]).edge_orbits()</span>
<span class="sd">          {0: set([0, 1, 2])}</span>
<span class="sd">          </span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">orbits</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(</span> <span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="nb">set</span><span class="p">([</span><span class="n">x</span><span class="p">]))</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span> <span class="p">)</span>
        <span class="k">for</span> <span class="n">a</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">automorphisms</span><span class="p">():</span>
            <span class="n">edge_permutation</span> <span class="o">=</span> <span class="n">a</span><span class="o">.</span><span class="n">pe</span>
            <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">):</span>
                <span class="k">if</span> <span class="n">x</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">orbits</span><span class="p">:</span>
                    <span class="k">continue</span>
                <span class="n">y</span> <span class="o">=</span> <span class="n">edge_permutation</span><span class="p">[</span><span class="n">x</span><span class="p">]</span>
                <span class="k">if</span> <span class="n">y</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">orbits</span><span class="p">:</span>
                    <span class="k">continue</span>
                <span class="c"># `x` and `y` are in the same orbit, only keep the one</span>
                <span class="c"># with lower abs. value, and remove the other.</span>
                <span class="k">if</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="n">x</span><span class="p">:</span>
                    <span class="n">orbits</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">orbits</span><span class="p">[</span><span class="n">y</span><span class="p">])</span>
                    <span class="k">del</span> <span class="n">orbits</span><span class="p">[</span><span class="n">y</span><span class="p">]</span>
        <span class="c"># check that all elements lie in some orbit</span>
        <span class="k">assert</span> <span class="nb">sum</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="n">o</span><span class="p">))</span> <span class="k">for</span> <span class="n">o</span> <span class="ow">in</span> <span class="n">orbits</span><span class="o">.</span><span class="n">itervalues</span><span class="p">())</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">,</span> \
               <span class="s">&quot;Fatgraph.edge_orbits():&quot;</span> \
               <span class="s">&quot; Computed orbits `</span><span class="si">%s</span><span class="s">` do not exhaust edge set `</span><span class="si">%s</span><span class="s">`&quot;</span> \
               <span class="s">&quot; [</span><span class="si">%s</span><span class="s">.edge_orbits() -&gt; </span><span class="si">%s</span><span class="s">]&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">orbits</span><span class="p">,</span> <span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">),</span> <span class="bp">self</span><span class="p">,</span> <span class="n">orbits</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">orbits</span>

</div>
    <span class="nd">@ocache0</span>
<div class="viewcode-block" id="Fatgraph.edge_pair_orbits"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.edge_pair_orbits">[docs]</a>    <span class="k">def</span> <span class="nf">edge_pair_orbits</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Compute orbits of pairs `(edge1, edge2)` under the action</span>
<span class="sd">        of graph automorphism group, and a representative for each</span>
<span class="sd">        orbit.</span>
<span class="sd">        </span>
<span class="sd">        Returns a dictionary, whose keys are the representatives, and</span>
<span class="sd">        whose values are the orbits.  Orbits are represented as Python</span>
<span class="sd">        `set` objects.</span>

<span class="sd">        Examples::</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([0,1,2]), Vertex([0,1,2])]).edge_pair_orbits()</span>
<span class="sd">          {(0, 1): set([(0, 1), (1, 2), (2, 0)]),</span>
<span class="sd">           (0, 0): set([(0, 0), (1, 1), (2, 2)]),</span>
<span class="sd">           (0, 2): set([(1, 0), (0, 2), (2, 1)])}</span>
<span class="sd">          </span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">edge_pairs</span> <span class="o">=</span> <span class="p">[</span> <span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">)</span> 
                       <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span>
                       <span class="k">for</span> <span class="n">y</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span><span class="p">)</span> <span class="p">]</span>
        <span class="n">orbits</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(</span> <span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="nb">set</span><span class="p">([</span><span class="n">p</span><span class="p">]))</span> <span class="k">for</span> <span class="n">p</span> <span class="ow">in</span> <span class="n">edge_pairs</span> <span class="p">)</span>
        <span class="k">for</span> <span class="n">a</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">automorphisms</span><span class="p">():</span>
            <span class="n">edge_permutation</span> <span class="o">=</span> <span class="n">a</span><span class="o">.</span><span class="n">pe</span>
            <span class="k">for</span> <span class="n">p</span> <span class="ow">in</span> <span class="n">edge_pairs</span><span class="p">:</span>
                <span class="k">if</span> <span class="n">p</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">orbits</span><span class="p">:</span>
                    <span class="k">continue</span>
                <span class="n">q</span> <span class="o">=</span> <span class="p">(</span><span class="n">edge_permutation</span><span class="p">[</span><span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]],</span> <span class="n">edge_permutation</span><span class="p">[</span><span class="n">p</span><span class="p">[</span><span class="mi">1</span><span class="p">]])</span>
                <span class="k">if</span> <span class="n">q</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">orbits</span><span class="p">:</span>
                    <span class="k">continue</span>
                <span class="c"># `p` and `q` are in the same orbit, only keep the one</span>
                <span class="c"># with lower abs. value, and remove the other.</span>
                <span class="k">if</span> <span class="n">p</span> <span class="o">&lt;</span> <span class="n">q</span><span class="p">:</span>
                    <span class="n">orbits</span><span class="p">[</span><span class="n">p</span><span class="p">]</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">orbits</span><span class="p">[</span><span class="n">q</span><span class="p">])</span>
                    <span class="k">del</span> <span class="n">orbits</span><span class="p">[</span><span class="n">q</span><span class="p">]</span>
        <span class="c"># check that all elements lie in some orbit</span>
        <span class="k">assert</span> <span class="nb">sum</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="n">o</span><span class="p">))</span> <span class="k">for</span> <span class="n">o</span> <span class="ow">in</span> <span class="n">orbits</span><span class="o">.</span><span class="n">itervalues</span><span class="p">())</span> <span class="o">==</span> <span class="nb">len</span><span class="p">(</span><span class="n">edge_pairs</span><span class="p">),</span> \
               <span class="s">&quot;Fatgraph.edge_pair_orbits():&quot;</span> \
               <span class="s">&quot; Computed orbits `</span><span class="si">%s</span><span class="s">` do not exhaust edge pairs set `</span><span class="si">%s</span><span class="s">`&quot;</span> \
               <span class="s">&quot; [</span><span class="si">%s</span><span class="s">.edge_pair_orbits() -&gt; </span><span class="si">%s</span><span class="s">]&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">orbits</span><span class="p">,</span> <span class="n">edge_pairs</span><span class="p">,</span> <span class="bp">self</span><span class="p">,</span> <span class="n">orbits</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">orbits</span>

</div>
<div class="viewcode-block" id="Fatgraph.endpoints"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.endpoints">[docs]</a>    <span class="k">def</span> <span class="nf">endpoints</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">edgeno</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return the endpoints of `edge`, as a pair of `(v, pos)`</span>
<span class="sd">        where `v` is the endpoint vertex index, and `pos` is the</span>
<span class="sd">        attachment index of `edge` into the `Vertex` object</span>
<span class="sd">        `self.vertices[v]`.</span>

<span class="sd">        The pair `((v1, pos1), (v2, pos2))` is ordered such that `v1 &lt; v2`.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">edgeno</span><span class="p">]</span><span class="o">.</span><span class="n">endpoints</span>

</div>
<div class="viewcode-block" id="Fatgraph.hangcircle"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.hangcircle">[docs]</a>    <span class="k">def</span> <span class="nf">hangcircle</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">edge</span><span class="p">,</span> <span class="n">side</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return a new `Fatgraph`, formed by attaching a circle with</span>
<span class="sd">        a new edge to a new trivalent vertex in the middle of `edge`.</span>

<span class="sd">          &gt;&gt;&gt; g = Fatgraph([Vertex([0,1,2]), Vertex([0,2,1])])</span>
<span class="sd">          &gt;&gt;&gt; g1 = g.hangcircle(0, 0)</span>
<span class="sd">          &gt;&gt;&gt; g1 is g</span>
<span class="sd">          False</span>
<span class="sd">          </span>
<span class="sd">        Argument `side` controls which side of `edge` the circle is</span>
<span class="sd">        hung to (valid values are 0 or 1), i.e., which of the two</span>
<span class="sd">        inequivalent cyclic orders the new trivalent vertices will be</span>
<span class="sd">        given::</span>
<span class="sd">        </span>
<span class="sd">          &gt;&gt;&gt; g = Fatgraph([Vertex([0,1,2]), Vertex([0,2,1])])</span>
<span class="sd">          &gt;&gt;&gt; g1 = g.hangcircle(0, 0)</span>
<span class="sd">          &gt;&gt;&gt; g1 == Fatgraph([Vertex([0,1,2]), Vertex([3,2,1]), Vertex([0,3,4]), Vertex([5,5,4])])</span>
<span class="sd">          True</span>
<span class="sd">          &gt;&gt;&gt; g2 = g.hangcircle(0, 1)</span>
<span class="sd">          &gt;&gt;&gt; g2 == Fatgraph([Vertex([0,1,2]), Vertex([3,2,1]), Vertex([3,0,4]), Vertex([5,5,4])])</span>
<span class="sd">          True</span>

<span class="sd">        It is worth noting that the new graph will have 3 edges more</span>
<span class="sd">        than the original one::</span>

<span class="sd">          &gt;&gt;&gt; g1.num_edges == g.num_edges + 3</span>
<span class="sd">          True</span>
<span class="sd">          </span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="n">side</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">],</span> \
               <span class="s">&quot;Fatgraph.hangcircle: Invalid value for `side`: &#39;</span><span class="si">%s</span><span class="s">&#39; - should be 0 or 1&quot;</span> <span class="o">%</span> <span class="n">side1</span>
        
        <span class="n">opposite_side</span> <span class="o">=</span> <span class="mi">0</span> <span class="k">if</span> <span class="n">side</span> <span class="k">else</span> <span class="mi">1</span>

        <span class="c">## assign edge indices</span>
        
        <span class="c">## break `edge` in two halves: if `v1` and `v2` are the</span>
        <span class="c">## endpoints of `edge`, then the &quot;one_half&quot; edge extends from</span>
        <span class="c">## the `v1` endpoint of `edge1` to the new vertex</span>
        <span class="c">## `midpoint`; the &quot;other_half&quot; edge extends from the</span>
        <span class="c">## `midpoint` new vertex to `v2`.</span>
        <span class="n">one_half</span> <span class="o">=</span> <span class="n">edge</span>
        <span class="n">other_half</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span>
        <span class="n">connecting_edge</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">+</span> <span class="mi">1</span>
        <span class="n">circling_edge</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">+</span> <span class="mi">2</span>
        
        <span class="c">## assign new indices to new vertices</span>
        <span class="n">midpoint_index</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span>
        <span class="n">T_index</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span> <span class="o">+</span> <span class="mi">1</span>

        <span class="c">## two new vertices are added: the mid-point of `edge`, and</span>
        <span class="c">## the vertex `T` lying on the circle.</span>
        <span class="k">if</span> <span class="n">side</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
            <span class="n">midpoint</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">other_half</span><span class="p">,</span> <span class="n">one_half</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>
        <span class="k">else</span><span class="p">:</span> <span class="c"># side == 0</span>
            <span class="n">midpoint</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">one_half</span><span class="p">,</span> <span class="n">other_half</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>
        <span class="n">T</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">([</span><span class="n">circling_edge</span><span class="p">,</span> <span class="n">circling_edge</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">])</span>
        <span class="n">new_vertices</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span> <span class="o">+</span> <span class="p">[</span><span class="n">midpoint</span><span class="p">,</span> <span class="n">T</span><span class="p">]</span>

        <span class="c">## new edges:</span>
        <span class="c">## - inherit edges from parent, and add place for three new edges</span>
        <span class="n">new_edges</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span> <span class="o">+</span> <span class="p">[</span>
            <span class="bp">None</span><span class="p">,</span> <span class="c"># new edge: other_half</span>
            <span class="bp">None</span><span class="p">,</span> <span class="c"># new edge: connecting_edge</span>
            <span class="bp">None</span><span class="p">,</span> <span class="c"># new edge: circling_edge</span>
            <span class="p">]</span>
        
        <span class="c">## - break `edge` into two edges `one_half` and `other_half`:</span>
        <span class="p">((</span><span class="n">v1</span><span class="p">,</span> <span class="n">pos1</span><span class="p">),</span> <span class="p">(</span><span class="n">v2</span><span class="p">,</span> <span class="n">pos2</span><span class="p">))</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">edge</span><span class="p">]</span><span class="o">.</span><span class="n">endpoints</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">one_half</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">v1</span><span class="p">,</span> <span class="n">pos1</span><span class="p">),</span> <span class="p">(</span><span class="n">midpoint_index</span><span class="p">,</span> <span class="n">side</span><span class="p">))</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">other_half</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">midpoint_index</span><span class="p">,</span> <span class="n">opposite_side</span><span class="p">),</span> <span class="p">(</span><span class="n">v2</span><span class="p">,</span> <span class="n">pos2</span><span class="p">))</span>
        <span class="n">new_vertices</span><span class="p">[</span><span class="n">v2</span><span class="p">]</span> <span class="o">=</span> <span class="n">Vertex</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">[</span><span class="n">v2</span><span class="p">][:</span><span class="n">pos2</span><span class="p">]</span>
                                             <span class="o">+</span> <span class="p">[</span><span class="n">other_half</span><span class="p">]</span>
                                             <span class="o">+</span> <span class="n">new_vertices</span><span class="p">[</span><span class="n">v2</span><span class="p">][</span><span class="n">pos2</span><span class="o">+</span><span class="mi">1</span><span class="p">:])</span>

        <span class="c">## - the connecting edge has endpoints in the mid-point of</span>
        <span class="c">## `edge` and in `T`, and is *always* in third position:</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">connecting_edge</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">midpoint_index</span><span class="p">,</span> <span class="mi">2</span><span class="p">),</span> <span class="p">(</span><span class="n">T_index</span><span class="p">,</span> <span class="mi">2</span><span class="p">))</span>

        <span class="c">## - the circling edge is a loop with vertex `T`</span>
        <span class="n">new_edges</span><span class="p">[</span><span class="n">circling_edge</span><span class="p">]</span> <span class="o">=</span> <span class="n">Edge</span><span class="p">((</span><span class="n">T_index</span><span class="p">,</span> <span class="mi">0</span><span class="p">),</span> <span class="p">(</span><span class="n">T_index</span><span class="p">,</span> <span class="mi">1</span><span class="p">))</span>

        <span class="c">## Inherit edge numbering from parent and extend as identity</span>
        <span class="c">## on the newly-added edges.</span>
        <span class="n">new_edge_numbering</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">edge_numbering</span> <span class="o">+</span> \
                             <span class="p">[</span><span class="n">other_half</span><span class="p">,</span> <span class="n">connecting_edge</span><span class="p">,</span> <span class="n">circling_edge</span><span class="p">]</span>

        <span class="c"># finally, build new graph </span>
        <span class="k">return</span> <span class="n">Fatgraph</span><span class="p">(</span><span class="n">new_vertices</span><span class="p">,</span>
                        <span class="n">edges</span> <span class="o">=</span> <span class="n">new_edges</span><span class="p">,</span>
                        <span class="n">num_edges</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_edges</span> <span class="o">+</span> <span class="mi">3</span><span class="p">,</span>
                        <span class="n">orientation</span> <span class="o">=</span> <span class="n">new_edge_numbering</span><span class="p">,</span>
                        <span class="p">)</span>
    
</div>
<div class="viewcode-block" id="Fatgraph.is_loop"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.is_loop">[docs]</a>    <span class="k">def</span> <span class="nf">is_loop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">edge</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return `True` if `edge` is a loop (i.e., the two endpoint coincide).</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">edge</span><span class="p">]</span><span class="o">.</span><span class="n">is_loop</span><span class="p">()</span>
        
</div>
<div class="viewcode-block" id="Fatgraph.is_oriented"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.is_oriented">[docs]</a>    <span class="k">def</span> <span class="nf">is_oriented</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return `True` if `Fatgraph` is orientable.</span>

<span class="sd">        A `Fatgraph` is orientable iff it has no orientation-reversing</span>
<span class="sd">        automorphism.</span>

<span class="sd">        Enumerate all automorphisms, end exit with `False` result as</span>
<span class="sd">        soon as one orientation-reversing one is found.</span>

<span class="sd">        Examples::</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([1,0,1,0])]).is_oriented()</span>
<span class="sd">          False</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2, 0, 1]), Vertex([2, 0, 1])]).is_oriented()</span>
<span class="sd">          True</span>
<span class="sd">          </span>
<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2, 1, 0]), Vertex([2, 0, 1])]).is_oriented()</span>
<span class="sd">          False</span>
<span class="sd">          </span>
<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2, 1, 1]), Vertex([2, 0, 0])]).is_oriented()</span>
<span class="sd">          False</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([3, 2, 2, 0, 1]), Vertex([3, 1, 0])], \</span>
<span class="sd">                    numbering=[(0, CyclicTuple((2,))),  \</span>
<span class="sd">                               (1, CyclicTuple((0, 1))),  \</span>
<span class="sd">                               (2, CyclicTuple((3, 1))),  \</span>
<span class="sd">                               (3, CyclicTuple((0, 3, 2))) ]) \</span>
<span class="sd">                               .is_oriented()</span>
<span class="sd">          True</span>
<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([2, 3, 1]), Vertex([2, 1, 3, 0, 0])], \</span>
<span class="sd">                       numbering=[(0, CyclicTuple((0,))),  \</span>
<span class="sd">                                  (2, CyclicTuple((1, 3))),  \</span>
<span class="sd">                                  (3, CyclicTuple((3, 0, 2))),  \</span>
<span class="sd">                                  (1, CyclicTuple((2, 1))) ]) \</span>
<span class="sd">                               .is_oriented()</span>
<span class="sd">          True</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c">## Try to find an orientation-reversing automorphism the hard way</span>
        <span class="k">for</span> <span class="n">a</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">automorphisms</span><span class="p">():</span>
            <span class="k">if</span> <span class="n">a</span><span class="o">.</span><span class="n">is_orientation_reversing</span><span class="p">():</span>
                <span class="k">return</span> <span class="bp">False</span>
        <span class="c"># no orientation reversing automorphism found</span>
        <span class="k">return</span> <span class="bp">True</span>

</div>
    <span class="nd">@ocache_isomorphisms</span>
<div class="viewcode-block" id="Fatgraph.isomorphisms"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.isomorphisms">[docs]</a>    <span class="k">def</span> <span class="nf">isomorphisms</span><span class="p">(</span><span class="n">G1</span><span class="p">,</span> <span class="n">G2</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Iterate over `Fatgraph` isomorphisms from `G1` to `G2`.</span>

<span class="sd">        An isomorphism is represented by a tuple `(pv, rot, pe)` where:</span>

<span class="sd">          - `pv` is a permutation of ther vertices: the `i`-th vertex</span>
<span class="sd">            of `G1` is sent to the `pv[i]`-th vertex of `G2`, rotated</span>
<span class="sd">            by `rot[i]` places leftwards;</span>

<span class="sd">          - `pe` is a permutation of the edges: edge `i` in `G1` is</span>
<span class="sd">            mapped to edge `pe[i]` in `G2`.</span>

<span class="sd">        This method can iterate over the automorphism group of a</span>
<span class="sd">        graph::</span>

<span class="sd">          &gt;&gt;&gt; G1 = Fatgraph([Vertex([2, 1, 1]), Vertex([2, 0, 0])])</span>
<span class="sd">          &gt;&gt;&gt; for f in G1.isomorphisms(G1): print f</span>
<span class="sd">          ({0: 0, 1: 1}, [0, 0], {0: 0, 1: 1, 2: 2})</span>
<span class="sd">          ({0: 1, 1: 0}, [0, 0], {0: 1, 1: 0, 2: 2})</span>

<span class="sd">        Or it can find the isomorphisms between two given graphs::</span>

<span class="sd">          &gt;&gt;&gt; G2 = Fatgraph([Vertex([2, 2, 0]), Vertex([1, 1, 0])])</span>
<span class="sd">          &gt;&gt;&gt; for f in G1.isomorphisms(G2): print f</span>
<span class="sd">          ({0: 0, 1: 1}, [2, 2], {0: 1, 1: 2, 2: 0})</span>
<span class="sd">          ({0: 1, 1: 0}, [2, 2], {0: 2, 1: 1, 2: 0})</span>

<span class="sd">        If there are no isomorphisms connecting the two graphs, then no</span>
<span class="sd">        item is returned by the iterator::</span>

<span class="sd">          &gt;&gt;&gt; g3 = Fatgraph([Vertex([2, 1, 0]), Vertex([2, 0, 1])])</span>
<span class="sd">          &gt;&gt;&gt; list(G1.isomorphisms(g3))</span>
<span class="sd">          []</span>

<span class="sd">        A concrete example taken from `M_{1,4}`:latex: ::</span>

<span class="sd">          &gt;&gt;&gt; g1 = Fatgraph([Vertex([1, 0, 2]), Vertex([2, 1, 5]), Vertex([0, 4, 3]), Vertex([8, 5, 6]), Vertex([3, 6, 7, 7]), Vertex([8, 4, 9, 9])])</span>
<span class="sd">          &gt;&gt;&gt; g2 = Fatgraph([Vertex([1, 0, 5, 6]), Vertex([1, 0, 2]), Vertex([5, 2, 3]), Vertex([8, 4, 3]), Vertex([7, 7, 6]), Vertex([4, 8, 9, 9])])</span>
<span class="sd">          &gt;&gt;&gt; len(list(Fatgraph.isomorphisms(g1, g2)))</span>
<span class="sd">          0</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c"># if graphs differ in vertex valences, no isomorphisms</span>
        <span class="n">vs1</span> <span class="o">=</span> <span class="n">G1</span><span class="o">.</span><span class="n">_valence_spectrum</span><span class="p">()</span>
        <span class="n">vs2</span> <span class="o">=</span> <span class="n">G2</span><span class="o">.</span><span class="n">_valence_spectrum</span><span class="p">()</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="nb">set</span><span class="p">(</span><span class="n">vs1</span><span class="o">.</span><span class="n">keys</span><span class="p">())</span> <span class="o">==</span> <span class="nb">set</span><span class="p">(</span><span class="n">vs2</span><span class="o">.</span><span class="n">keys</span><span class="p">()):</span>
            <span class="k">return</span> <span class="c"># StopIteration</span>
        <span class="c"># if graphs have unequal vertex distribution by valence, no isomorphisms</span>
        <span class="k">for</span> <span class="n">val</span> <span class="ow">in</span> <span class="n">G1</span><span class="o">.</span><span class="n">vertex_valences</span><span class="p">():</span>
            <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">vs1</span><span class="p">[</span><span class="n">val</span><span class="p">])</span> <span class="o">!=</span> <span class="nb">len</span><span class="p">(</span><span class="n">vs2</span><span class="p">[</span><span class="n">val</span><span class="p">]):</span>
                <span class="k">return</span> <span class="c"># StopIteration</span>

        <span class="p">(</span><span class="n">valence</span><span class="p">,</span> <span class="n">indexes</span><span class="p">)</span> <span class="o">=</span> <span class="n">G2</span><span class="o">.</span><span class="n">_starting_vertices</span><span class="p">()</span>
        <span class="n">v1_index</span> <span class="o">=</span> <span class="n">vs1</span><span class="p">[</span><span class="n">valence</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span>
        <span class="n">v1</span> <span class="o">=</span> <span class="n">G1</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v1_index</span><span class="p">]</span>
        <span class="k">for</span> <span class="n">v2_index</span> <span class="ow">in</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_compatible_vertices</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span> <span class="n">G2</span><span class="p">,</span> <span class="n">indexes</span><span class="p">):</span>
            <span class="k">for</span> <span class="n">rot</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="n">valence</span><span class="p">):</span>
                <span class="k">try</span><span class="p">:</span>
                    <span class="c"># pass 0: init new (pv, rots, pe) triple</span>
                    <span class="n">pv</span> <span class="o">=</span> <span class="n">Permutation</span><span class="p">()</span>
                    <span class="n">rots</span> <span class="o">=</span> <span class="p">[</span> <span class="bp">None</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="n">G1</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">)</span> <span class="p">]</span>
                    <span class="n">pe</span> <span class="o">=</span> <span class="n">Permutation</span><span class="p">()</span>

                    <span class="c"># pass 1: map `v1` to `v2` and build map</span>
                    <span class="c"># of neighboring vertices for next pass</span>
                    <span class="k">if</span> <span class="ow">not</span> <span class="n">pe</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span> <span class="n">G2</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v2_index</span><span class="p">][</span><span class="n">rot</span><span class="p">:</span><span class="n">rot</span><span class="o">+</span><span class="n">valence</span><span class="p">]):</span>
                        <span class="k">continue</span> <span class="c"># to next `rot`</span>
                    <span class="n">pv</span><span class="p">[</span><span class="n">v1_index</span><span class="p">]</span> <span class="o">=</span> <span class="n">v2_index</span>
                    <span class="n">rots</span><span class="p">[</span><span class="n">v1_index</span><span class="p">]</span> <span class="o">=</span> <span class="n">rot</span>
                    <span class="k">if</span> <span class="n">__debug__</span><span class="p">:</span>
                        <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">v1</span><span class="p">:</span>
                            <span class="k">assert</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">pe</span><span class="p">,</span> <span class="s">&quot;Edge `</span><span class="si">%d</span><span class="s">` of vertex `</span><span class="si">%s</span><span class="s">` (in graph `</span><span class="si">%s</span><span class="s">`) not mapped to any edge of graph `</span><span class="si">%s</span><span class="s">` (at line 1740, `pe=</span><span class="si">%s</span><span class="s">`)&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">v1</span><span class="p">,</span> <span class="n">G1</span><span class="p">,</span> <span class="n">G2</span><span class="p">,</span> <span class="n">pe</span><span class="p">)</span>

                    <span class="c"># pass 2: extend map to neighboring vertices</span>
                    <span class="n">nexts</span> <span class="o">=</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_neighbors</span><span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">pe</span><span class="p">,</span> <span class="n">G1</span><span class="p">,</span> <span class="n">v1_index</span><span class="p">,</span> <span class="n">G2</span><span class="p">,</span> <span class="n">v2_index</span><span class="p">)</span>
                    <span class="k">while</span> <span class="nb">len</span><span class="p">(</span><span class="n">pv</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">G1</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">:</span>
                        <span class="n">neighborhood</span> <span class="o">=</span> <span class="p">[]</span>
                        <span class="k">for</span> <span class="p">(</span><span class="n">i1</span><span class="p">,</span> <span class="n">i2</span><span class="p">,</span> <span class="n">r</span><span class="p">)</span> <span class="ow">in</span> <span class="n">nexts</span><span class="p">:</span>
                            <span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">rots</span><span class="p">,</span> <span class="n">pe</span><span class="p">)</span> <span class="o">=</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_extend_map</span><span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">rots</span><span class="p">,</span> <span class="n">pe</span><span class="p">,</span> <span class="n">G1</span><span class="p">,</span> <span class="n">i1</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">G2</span><span class="p">,</span> <span class="n">i2</span><span class="p">)</span>
                            <span class="k">if</span> <span class="n">__debug__</span><span class="p">:</span>
                                <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">G1</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">i1</span><span class="p">]:</span>
                                    <span class="k">assert</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">pe</span><span class="p">,</span> <span class="s">&quot;Edge `</span><span class="si">%d</span><span class="s">` of vertex `</span><span class="si">%s</span><span class="s">` (in graph `</span><span class="si">%s</span><span class="s">`) not mapped to any edge of graph `</span><span class="si">%s</span><span class="s">` (at line 1751, `pe=</span><span class="si">%s</span><span class="s">`)&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">G1</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">i1</span><span class="p">],</span> <span class="n">G1</span><span class="p">,</span> <span class="n">G2</span><span class="p">,</span> <span class="n">pe</span><span class="p">)</span>
                            <span class="n">neighborhood</span> <span class="o">+=</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_neighbors</span><span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">pe</span><span class="p">,</span> <span class="n">G1</span><span class="p">,</span> <span class="n">i1</span><span class="p">,</span> <span class="n">G2</span><span class="p">,</span> <span class="n">i2</span><span class="p">)</span>
                        <span class="n">nexts</span> <span class="o">=</span> <span class="n">neighborhood</span>

                <span class="c"># extension failed in the above block, continue with next candidate</span>
                <span class="k">except</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_CannotExtendMap</span><span class="p">:</span>
                    <span class="k">continue</span> <span class="c"># to next `rot`</span>

                <span class="c"># finally</span>
                <span class="k">yield</span> <span class="n">Isomorphism</span><span class="p">(</span><span class="n">G1</span><span class="p">,</span> <span class="n">G2</span><span class="p">,</span> <span class="n">pv</span><span class="p">,</span> <span class="n">rots</span><span class="p">,</span> <span class="n">pe</span><span class="p">)</span>

    <span class="c">## auxiliary functions for `Fatgraph.isomorphism`</span>
</div>
    <span class="nd">@ocache0</span>
    <span class="k">def</span> <span class="nf">_valence_spectrum</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return a dictionary mapping valences into vertex indices.</span>

<span class="sd">        Examples::</span>

<span class="sd">           &gt;&gt;&gt; Fatgraph([Vertex([1,1,0,0])])._valence_spectrum()</span>
<span class="sd">           defaultdict(&lt;type &#39;list&#39;&gt;, {4: [0]})</span>

<span class="sd">           &gt;&gt;&gt; Fatgraph([Vertex([1,1,0]), Vertex([2,2,0])])._valence_spectrum()</span>
<span class="sd">           defaultdict(&lt;type &#39;list&#39;&gt;, {3: [0, 1]})</span>

<span class="sd">           &gt;&gt;&gt; Fatgraph([Vertex([3, 1, 0, 1]), \</span>
<span class="sd">                      Vertex([4, 4, 0]), Vertex([3, 2, 2])])._valence_spectrum()</span>
<span class="sd">           defaultdict(&lt;type &#39;list&#39;&gt;, {3: [1, 2], 4: [0]})</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">result</span> <span class="o">=</span> <span class="n">defaultdict</span><span class="p">(</span><span class="nb">list</span><span class="p">)</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">index</span><span class="p">,</span> <span class="n">vertex</span><span class="p">)</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">):</span>
            <span class="n">l</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">vertex</span><span class="p">)</span>
            <span class="n">result</span><span class="p">[</span><span class="n">l</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">index</span><span class="p">)</span>
        <span class="c"># consistency checks</span>
        <span class="k">assert</span> <span class="nb">set</span><span class="p">(</span><span class="n">result</span><span class="o">.</span><span class="n">keys</span><span class="p">())</span> <span class="o">==</span> <span class="nb">set</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertex_valences</span><span class="p">()),</span> \
               <span class="s">&quot;Fatgraph.valence_spectrum:&quot;</span> \
               <span class="s">&quot;Computed valence spectrum `</span><span class="si">%s</span><span class="s">` does not exhaust all &quot;</span> \
               <span class="s">&quot; vertex valences </span><span class="si">%s</span><span class="s">&quot;</span> \
               <span class="o">%</span> <span class="p">(</span><span class="n">result</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertex_valences</span><span class="p">())</span>
        <span class="k">assert</span> <span class="nb">set</span><span class="p">(</span><span class="n">concat</span><span class="p">(</span><span class="n">result</span><span class="o">.</span><span class="n">values</span><span class="p">()))</span> \
               <span class="o">==</span> <span class="nb">set</span><span class="p">(</span><span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">)),</span> \
               <span class="s">&quot;Fatgraph.valence_spectrum:&quot;</span> \
               <span class="s">&quot;Computed valence spectrum `</span><span class="si">%s</span><span class="s">` does not exhaust all &quot;</span> \
               <span class="s">&quot; </span><span class="si">%d</span><span class="s"> vertex indices&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">result</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">num_vertices</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="nd">@ocache0</span>
    <span class="k">def</span> <span class="nf">_starting_vertices</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Return the pair `(valence, vertices)`, which minimizes the</span>
<span class="sd">        product of valence with the number of vertices of that</span>
<span class="sd">        valence.  The `vertices` part of the pair is the list of</span>
<span class="sd">        indices in `self.vertices` corresponding to vertices with the</span>
<span class="sd">        chosen valence.</span>

<span class="sd">        Examples::</span>

<span class="sd">          &gt;&gt;&gt; g = Fatgraph([Vertex([0,1,2]), Vertex([0,2,3]),</span>
<span class="sd">          ...              Vertex([3,4,4,5,5]), Vertex([1,6,6])])</span>
<span class="sd">          &gt;&gt;&gt; g._starting_vertices()</span>
<span class="sd">          (5, [2])</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">val</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertex_valences</span><span class="p">())</span>
        <span class="n">vs</span> <span class="o">=</span> <span class="bp">None</span>
        <span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">)</span><span class="o">+</span><span class="mi">1</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">val_</span><span class="p">,</span> <span class="n">vs_</span><span class="p">)</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_valence_spectrum</span><span class="p">()</span><span class="o">.</span><span class="n">iteritems</span><span class="p">():</span>
            <span class="n">n_</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">vs_</span><span class="p">)</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">n_</span><span class="o">*</span><span class="n">val_</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">*</span><span class="n">val</span><span class="p">)</span> \
                   <span class="ow">or</span> <span class="p">(</span><span class="n">n_</span><span class="o">*</span><span class="n">val_</span> <span class="o">==</span> <span class="n">n</span><span class="o">*</span><span class="n">val</span> <span class="ow">and</span> <span class="n">val_</span><span class="o">&lt;</span><span class="n">val</span><span class="p">):</span>
                <span class="n">val</span> <span class="o">=</span> <span class="n">val_</span>
                <span class="n">vs</span> <span class="o">=</span> <span class="n">vs_</span>
                <span class="n">n</span> <span class="o">=</span> <span class="n">n_</span>
        <span class="k">return</span> <span class="p">(</span><span class="n">val</span><span class="p">,</span> <span class="n">vs</span><span class="p">)</span>

    <span class="nd">@staticmethod</span>
    <span class="k">def</span> <span class="nf">_compatible</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span> <span class="n">v2</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return `True` if vertices `v1` and `v2` are compatible.</span>
<span class="sd">        (i.e., same valence and number of loops - one *could* be</span>
<span class="sd">        mapped onto the other.)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">v1</span><span class="p">)</span> <span class="o">==</span> <span class="nb">len</span><span class="p">(</span><span class="n">v2</span><span class="p">)</span> <span class="ow">and</span> <span class="n">v1</span><span class="o">.</span><span class="n">num_loops</span> <span class="o">==</span> <span class="n">v2</span><span class="o">.</span><span class="n">num_loops</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">True</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">False</span>

    <span class="nd">@staticmethod</span>
    <span class="k">def</span> <span class="nf">_compatible_vertices</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">g</span><span class="p">,</span> <span class="n">ixs</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Iterate over all (indices of) vertices in `g`, which</span>
<span class="sd">        `v` *could* be mapped to (that is, the destination vertex</span>
<span class="sd">        matches `v` in valence and number of loops.</span>

<span class="sd">        Third argument `ixs` restricts the search to the given</span>
<span class="sd">        subset of vertex indices in `g`.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">ixs</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_compatible</span><span class="p">(</span><span class="n">v</span><span class="p">,</span> <span class="n">g</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">i</span><span class="p">]):</span>
                <span class="k">yield</span> <span class="n">i</span>

    <span class="k">class</span> <span class="nc">_CannotExtendMap</span><span class="p">(</span><span class="ne">Exception</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Exception raised by `extend_map` on failure to extend a</span>
<span class="sd">        partial map.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">pass</span>

    <span class="nd">@staticmethod</span>
    <span class="k">def</span> <span class="nf">_extend_map</span><span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">rots</span><span class="p">,</span> <span class="n">pe</span><span class="p">,</span> <span class="n">G1</span><span class="p">,</span> <span class="n">i1</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">G2</span><span class="p">,</span> <span class="n">i2</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Extend map `(pv, rots, pe)` by mapping the `i1`-th</span>
<span class="sd">        vertex in `G1` to the `i2`-th vertex in `G2` (and rotating</span>
<span class="sd">        the source vertex by `r` places leftwards).  Return the</span>
<span class="sd">        extended map `(pv, rot, pe)`.</span>

<span class="sd">        The partial map is a triple `(pv, rot, pe)` as in</span>
<span class="sd">        `Fatgraph.isomorphism` (which see), with the additional</span>
<span class="sd">        proviso that unassigned items in `rot` are represented by</span>
<span class="sd">        `None`.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">v1</span> <span class="o">=</span> <span class="n">G1</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">i1</span><span class="p">]</span>
        <span class="n">v2</span> <span class="o">=</span> <span class="n">G2</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">i2</span><span class="p">]</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_compatible</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span> <span class="n">v2</span><span class="p">):</span>
            <span class="k">raise</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_CannotExtendMap</span>

        <span class="c"># XXX: rotation has to be &gt;=0 for the [r:r+..] shift below to work</span>
        <span class="k">if</span> <span class="n">r</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
            <span class="n">r</span> <span class="o">+=</span> <span class="nb">len</span><span class="p">(</span><span class="n">v2</span><span class="p">)</span>

        <span class="k">if</span> <span class="n">i1</span> <span class="ow">in</span> <span class="n">pv</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">pv</span><span class="p">[</span><span class="n">i1</span><span class="p">]</span> <span class="o">!=</span> <span class="n">i2</span> <span class="ow">or</span> <span class="p">(</span><span class="n">rots</span><span class="p">[</span><span class="n">i1</span><span class="p">]</span> <span class="o">-</span> <span class="n">r</span><span class="p">)</span> <span class="o">%</span> <span class="nb">len</span><span class="p">(</span><span class="n">v2</span><span class="p">)</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">:</span>
                <span class="k">raise</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_CannotExtendMap</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="c"># this pair has already been added</span>
                <span class="k">return</span> <span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">rots</span><span class="p">,</span> <span class="n">pe</span><span class="p">)</span>

        <span class="n">i</span> <span class="o">=</span> <span class="n">pv</span><span class="o">.</span><span class="n">find</span><span class="p">(</span><span class="n">i2</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">i</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span> <span class="c"># i.e., i in pv.values()</span>
            <span class="k">if</span> <span class="n">i</span> <span class="o">!=</span> <span class="n">i1</span> <span class="ow">or</span> <span class="p">(</span><span class="n">rots</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="n">r</span><span class="p">)</span> <span class="o">%</span> <span class="nb">len</span><span class="p">(</span><span class="n">v2</span><span class="p">)</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">:</span>
                <span class="k">raise</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_CannotExtendMap</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="c"># this pair has already been added</span>
                <span class="k">return</span> <span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">rots</span><span class="p">,</span> <span class="n">pe</span><span class="p">)</span>

        <span class="c"># rotating `v1` leftwards is equivalent to rotating `v2` rightwards...</span>
        <span class="n">v2</span> <span class="o">=</span> <span class="n">v2</span><span class="p">[</span><span class="n">r</span><span class="p">:</span><span class="n">r</span><span class="o">+</span><span class="nb">len</span><span class="p">(</span><span class="n">v2</span><span class="p">)]</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="n">pe</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span> <span class="n">v2</span><span class="p">):</span>
            <span class="k">raise</span> <span class="n">Fatgraph</span><span class="o">.</span><span class="n">_CannotExtendMap</span>

        <span class="n">pv</span><span class="p">[</span><span class="n">i1</span><span class="p">]</span> <span class="o">=</span> <span class="n">i2</span>
        <span class="n">rots</span><span class="p">[</span><span class="n">i1</span><span class="p">]</span> <span class="o">=</span> <span class="n">r</span>
        <span class="k">return</span> <span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">rots</span><span class="p">,</span> <span class="n">pe</span><span class="p">)</span>

    <span class="nd">@staticmethod</span>
    <span class="k">def</span> <span class="nf">_neighbors</span><span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">pe</span><span class="p">,</span> <span class="n">G1</span><span class="p">,</span> <span class="n">v1</span><span class="p">,</span> <span class="n">G2</span><span class="p">,</span> <span class="n">v2</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;List of vertex-to-vertex mappings that extend map `pv`</span>
<span class="sd">        in the neighborhood of vertices `v1` (in the domain) and</span>
<span class="sd">        `v2` (in the codomain).</span>

<span class="sd">        Return a list of triplets `(src, dst, rot)`, where:</span>
<span class="sd">           * `src` is the index of a vertex in `G1`,</span>
<span class="sd">             connected to `v1` by an edge `x`;</span>
<span class="sd">           * `dst` is the index of a vertex in `G2`,</span>
<span class="sd">             connected to `v2` by the image (according to `pe`)</span>
<span class="sd">             of edge `x`;</span>
<span class="sd">           * `rot` is the rotation to be applied to `G1[src]`</span>
<span class="sd">             so that edge `x` and its image appear</span>
<span class="sd">             at the same index position;</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="n">v2</span> <span class="o">==</span> <span class="n">pv</span><span class="p">[</span><span class="n">v1</span><span class="p">]</span>
        <span class="n">result</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">G1</span><span class="o">.</span><span class="n">vertices</span><span class="p">[</span><span class="n">v1</span><span class="p">]:</span>
            <span class="k">if</span> <span class="n">G1</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">.</span><span class="n">is_loop</span><span class="p">():</span>
                <span class="k">continue</span> <span class="c"># with next edge `x`</span>
            <span class="p">((</span><span class="n">s1</span><span class="p">,</span> <span class="n">a1</span><span class="p">),</span> <span class="p">(</span><span class="n">s2</span><span class="p">,</span> <span class="n">a2</span><span class="p">))</span> <span class="o">=</span> <span class="n">G1</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">.</span><span class="n">endpoints</span>
            <span class="n">src_v</span><span class="p">,</span> <span class="n">src_i</span> <span class="o">=</span> <span class="p">(</span><span class="n">s2</span><span class="p">,</span><span class="n">a2</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">s1</span> <span class="o">==</span> <span class="n">v1</span><span class="p">)</span> <span class="k">else</span> <span class="p">(</span><span class="n">s1</span><span class="p">,</span><span class="n">a1</span><span class="p">)</span>
            <span class="c"># ignore vertices that are already in the domain of `m`</span>
            <span class="k">if</span> <span class="n">src_v</span> <span class="ow">in</span> <span class="n">pv</span><span class="o">.</span><span class="n">keys</span><span class="p">():</span>
                <span class="k">continue</span> <span class="c"># to next `x`</span>
            <span class="p">((</span><span class="n">d1</span><span class="p">,</span> <span class="n">b1</span><span class="p">),</span> <span class="p">(</span><span class="n">d2</span><span class="p">,</span> <span class="n">b2</span><span class="p">))</span> <span class="o">=</span> <span class="n">G2</span><span class="o">.</span><span class="n">edges</span><span class="p">[</span><span class="n">pe</span><span class="p">[</span><span class="n">x</span><span class="p">]]</span><span class="o">.</span><span class="n">endpoints</span>
            <span class="n">dst_v</span><span class="p">,</span> <span class="n">dst_i</span> <span class="o">=</span> <span class="p">(</span><span class="n">d2</span><span class="p">,</span><span class="n">b2</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">d1</span> <span class="o">==</span> <span class="n">v2</span><span class="p">)</span> <span class="k">else</span> <span class="p">(</span><span class="n">d1</span><span class="p">,</span><span class="n">b1</span><span class="p">)</span>
            <span class="k">if</span> <span class="n">dst_v</span> <span class="ow">in</span> <span class="n">pv</span><span class="o">.</span><span class="n">values</span><span class="p">():</span>
                <span class="k">continue</span> <span class="c"># to next `x`</span>
            <span class="c"># array of (source vertex index, dest vertex index, rotation)</span>
            <span class="n">result</span><span class="o">.</span><span class="n">append</span><span class="p">((</span><span class="n">src_v</span><span class="p">,</span> <span class="n">dst_v</span><span class="p">,</span> <span class="n">dst_i</span><span class="o">-</span><span class="n">src_i</span><span class="p">))</span>
        <span class="k">return</span> <span class="n">result</span>


<div class="viewcode-block" id="Fatgraph.num_automorphisms"><a class="viewcode-back" href="../../api.html#fatghol.rg.Fatgraph.num_automorphisms">[docs]</a>    <span class="k">def</span> <span class="nf">num_automorphisms</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return the cardinality of the automorphism group of this</span>
<span class="sd">        `Fatgraph` object.</span>

<span class="sd">        Examples::</span>

<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([0,1,2]), Vertex([0,2,1])]).num_automorphisms()</span>
<span class="sd">          6</span>
<span class="sd">          &gt;&gt;&gt; Fatgraph([Vertex([0,1,1]), Vertex([0,2,2])]).num_automorphisms()</span>
<span class="sd">          2</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">automorphisms</span><span class="p">()))</span>
    
</div>
    <span class="nd">@ocache0</span>
    <span class="k">def</span> <span class="nf">vertex_valences</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="nb">frozenset</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">v</span><span class="p">)</span> <span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">vertices</span><span class="p">)</span>


    </div>
<div class="viewcode-block" id="MgnTrivalentGraphsRecursiveGenerator"><a class="viewcode-back" href="../../api.html#fatghol.rg.MgnTrivalentGraphsRecursiveGenerator">[docs]</a><span class="k">def</span> <span class="nf">MgnTrivalentGraphsRecursiveGenerator</span><span class="p">(</span><span class="n">g</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;Return a list of all connected trivalent fatgraphs having the</span>
<span class="sd">    prescribed genus `g` and number of boundary cycles `n`.</span>
<span class="sd">    </span>
<span class="sd">    Examples::</span>

<span class="sd">      &gt;&gt;&gt; for g in MgnTrivalentGraphsRecursiveGenerator(0,3): print g</span>
<span class="sd">      Fatgraph([Vertex([1, 2, 1]), Vertex([2, 0, 0])]) </span>
<span class="sd">      Fatgraph([Vertex([1, 0, 2]), Vertex([2, 0, 1])])</span>

<span class="sd">      &gt;&gt;&gt; for g in MgnTrivalentGraphsRecursiveGenerator(1,1): print g</span>
<span class="sd">      Fatgraph([Vertex([1, 0, 2]), Vertex([2, 1, 0])])</span>

<span class="sd">    &quot;&quot;&quot;</span>
    <span class="c"># avoid infinite recursion in later statements</span>
    <span class="k">if</span> <span class="n">n</span><span class="o">==</span><span class="mi">0</span> <span class="ow">or</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">)</span><span class="o">&lt;</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">):</span>
        <span class="k">raise</span> <span class="ne">StopIteration</span>

    <span class="c"># sanity check</span>
    <span class="k">assert</span> <span class="n">n</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">,</span> \
           <span class="s">&quot;MgnTrivalentGraphsRecursiveGenerator: &quot;</span> \
           <span class="s">&quot; number of boundary cycles `n` must be positive,&quot;</span>\
           <span class="s">&quot; but got `</span><span class="si">%s</span><span class="s">` instead&quot;</span> <span class="o">%</span> <span class="n">n</span>

    <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;Starting MgnTrivalentGraphsRecursiveGenerator(</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">) ...&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>

    <span class="c">## M_{0,3} - induction base</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">):</span>
        <span class="k">yield</span> <span class="n">Fatgraph</span><span class="p">([</span><span class="n">Vertex</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">]),</span> <span class="n">Vertex</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">])])</span>
        <span class="k">yield</span> <span class="n">Fatgraph</span><span class="p">([</span><span class="n">Vertex</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">2</span><span class="p">]),</span> <span class="n">Vertex</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">])])</span>
        <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;  MgnTrivalentGraphsRecursiveGenerator(0,3) done.&quot;</span><span class="p">)</span>

    <span class="c">## M_{1,1} - induction base</span>
    <span class="k">elif</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="p">):</span>
        <span class="k">yield</span> <span class="n">Fatgraph</span><span class="p">([</span><span class="n">Vertex</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">2</span><span class="p">]),</span> <span class="n">Vertex</span><span class="p">([</span><span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">])])</span>
        <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;  MgnTrivalentGraphsRecursiveGenerator(1,1) done.&quot;</span><span class="p">)</span>

    <span class="c">## General case</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="k">try</span><span class="p">:</span>
            <span class="n">checkpoint</span> <span class="o">=</span> <span class="n">os</span><span class="o">.</span><span class="n">path</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">runtime</span><span class="o">.</span><span class="n">options</span><span class="o">.</span><span class="n">checkpoint_dir</span><span class="p">,</span>
                                      <span class="p">(</span><span class="s">&quot;MgnTrivalentGraphsRecursiveGenerator</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">.list&quot;</span>
                                       <span class="o">%</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span> <span class="n">n</span><span class="p">)))</span>
        <span class="k">except</span> <span class="ne">AttributeError</span><span class="p">:</span>
            <span class="c"># test run, `runtime.options` not defined</span>
            <span class="n">checkpoint</span> <span class="o">=</span> <span class="bp">None</span>

        <span class="c"># try loading from file</span>
        <span class="n">unique</span> <span class="o">=</span> <span class="bp">None</span>
        <span class="k">if</span> <span class="n">checkpoint</span> <span class="ow">and</span> <span class="n">runtime</span><span class="o">.</span><span class="n">options</span><span class="o">.</span><span class="n">restart</span><span class="p">:</span>
            <span class="k">try</span><span class="p">:</span>
                <span class="n">unique</span> <span class="o">=</span> <span class="n">load</span><span class="p">(</span><span class="n">checkpoint</span><span class="p">)</span>
                <span class="k">if</span> <span class="n">unique</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
                    <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;  Loaded </span><span class="si">%d</span><span class="s"> trivalent graphs from file &#39;</span><span class="si">%s</span><span class="s">&#39;&quot;</span><span class="p">,</span>
                                  <span class="nb">len</span><span class="p">(</span><span class="n">unique</span><span class="p">),</span> <span class="n">checkpoint</span><span class="p">)</span>
            <span class="k">except</span> <span class="ne">Exception</span><span class="p">,</span> <span class="n">error</span><span class="p">:</span>
                <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;  Could not load saved state from file &#39;</span><span class="si">%s</span><span class="s">&#39;: </span><span class="si">%s</span><span class="s">&quot;</span><span class="p">,</span>
                              <span class="n">checkpoint</span><span class="p">,</span> <span class="n">error</span><span class="o">.</span><span class="n">message</span><span class="p">)</span>
                <span class="c"># ignore error and proceed</span>

        <span class="k">if</span> <span class="n">unique</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
            <span class="c"># could not restore from saved state, have to compute</span>
            <span class="n">unique</span> <span class="o">=</span> <span class="p">[</span> <span class="p">]</span>
            <span class="n">discarded</span> <span class="o">=</span> <span class="mi">0</span>
            <span class="n">timing</span><span class="o">.</span><span class="n">start</span><span class="p">(</span><span class="s">&quot;MgnTrivalentGraphsRecursiveGenerator(</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">)&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
            <span class="k">for</span> <span class="n">G</span> <span class="ow">in</span> <span class="n">_MgnTrivalentGraphsRecursiveGenerator_main</span><span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">):</span>
                <span class="c"># XXX: should this check be done in  *_main(g,n)?</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">G</span><span class="o">.</span><span class="n">genus</span><span class="p">,</span> <span class="n">G</span><span class="o">.</span><span class="n">num_boundary_cycles</span><span class="p">)</span> <span class="o">!=</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">)</span> <span class="ow">or</span> <span class="p">(</span><span class="n">G</span> <span class="ow">in</span> <span class="n">unique</span><span class="p">):</span>
                    <span class="n">discarded</span> <span class="o">+=</span> <span class="mi">1</span>
                    <span class="k">continue</span>
                <span class="n">unique</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">G</span><span class="p">)</span>
                <span class="k">yield</span> <span class="n">G</span>
            <span class="n">timing</span><span class="o">.</span><span class="n">stop</span><span class="p">(</span><span class="s">&quot;MgnTrivalentGraphsRecursiveGenerator(</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">)&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
            <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span>
                <span class="s">&quot;  MgnTrivalentGraphsRecursiveGenerator(</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">) done: </span><span class="si">%d</span><span class="s"> unique graphs, discarded </span><span class="si">%d</span><span class="s"> duplicates. (Elapsed: </span><span class="si">%.3f</span><span class="s">s)&quot;</span><span class="p">,</span> 
                <span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">unique</span><span class="p">),</span> <span class="n">discarded</span><span class="p">,</span> 
                <span class="n">timing</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s">&quot;MgnTrivalentGraphsRecursiveGenerator(</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">)&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">)))</span>
            <span class="c"># clear cached isomorphisms, they will not be needed in the sequel</span>
            <span class="k">for</span> <span class="n">G</span> <span class="ow">in</span> <span class="n">unique</span><span class="p">:</span>
                <span class="k">try</span><span class="p">:</span>
                    <span class="n">G</span><span class="o">.</span><span class="n">_cache_isomorphisms</span><span class="o">.</span><span class="n">clear</span><span class="p">()</span> <span class="c"># XXX: private impl. detail!</span>
                <span class="k">except</span> <span class="ne">AttributeError</span><span class="p">:</span>
                    <span class="k">pass</span>
            <span class="c"># save to checkpoint file (if defined)</span>
            <span class="k">if</span> <span class="n">checkpoint</span><span class="p">:</span>
                <span class="n">save</span><span class="p">(</span><span class="n">unique</span><span class="p">,</span> <span class="n">checkpoint</span><span class="p">)</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="c"># re-use loaded graphs</span>
            <span class="k">for</span> <span class="n">G</span> <span class="ow">in</span> <span class="n">unique</span><span class="p">:</span>
                <span class="k">yield</span> <span class="n">G</span>

</div>
<span class="k">def</span> <span class="nf">_MgnTrivalentGraphsRecursiveGenerator_main</span><span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">):</span>
    <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;  MgnTrivalentGraphsRecursiveGenerator(</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">): &quot;</span>
                  <span class="s">&quot;pass 1: hang a circle to all edges of graphs in M_{</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">} ...&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">,</span> <span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">))</span>
    <span class="k">for</span> <span class="n">G</span> <span class="ow">in</span> <span class="n">MgnTrivalentGraphsRecursiveGenerator</span><span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">G</span><span class="o">.</span><span class="n">edge_orbits</span><span class="p">():</span>
            <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">hangcircle</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">0</span><span class="p">)</span>
            <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">hangcircle</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>

    <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;  MgnTrivalentGraphsRecursiveGenerator(</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">): &quot;</span>
                  <span class="s">&quot;pass 2: bridge all edges of a single graph in M_{</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">} ...&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">,</span> <span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">))</span>
    <span class="k">for</span> <span class="n">G</span> <span class="ow">in</span> <span class="n">MgnTrivalentGraphsRecursiveGenerator</span><span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">):</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">)</span> <span class="ow">in</span> <span class="n">G</span><span class="o">.</span><span class="n">edge_pair_orbits</span><span class="p">():</span>
                <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">bridge</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span><span class="mi">0</span><span class="p">)</span>
                <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">bridge</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>
                <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">bridge</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span><span class="mi">0</span><span class="p">)</span>
                <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">bridge</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>

    <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;  MgnTrivalentGraphsRecursiveGenerator(</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">): &quot;</span>
                  <span class="s">&quot;pass 3: bridge all edges of a single graph in M_{</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">} ...&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">,</span> <span class="n">g</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span>
    <span class="k">for</span> <span class="n">G</span> <span class="ow">in</span> <span class="n">MgnTrivalentGraphsRecursiveGenerator</span><span class="p">(</span><span class="n">g</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">):</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">)</span> <span class="ow">in</span> <span class="n">G</span><span class="o">.</span><span class="n">edge_pair_orbits</span><span class="p">():</span>
                <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">bridge</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span><span class="mi">0</span><span class="p">)</span>
                <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">bridge</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>
                <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">bridge</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span><span class="mi">0</span><span class="p">)</span>
                <span class="k">yield</span> <span class="n">G</span><span class="o">.</span><span class="n">bridge</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>

    <span class="c">## logging.debug(&quot;  MgnTrivalentGraphsRecursiveGenerator(%d,%d): &quot;</span>
    <span class="c">##               &quot;pass 4: bridge two graphs of such that g_1+g_2=%d, n_1+n_2=%d ...&quot; % (g,n, g,n+1)) </span>
    <span class="c">## def add_up_to(x, min=0):</span>
    <span class="c">##     if x == 0 and min == 0:</span>
    <span class="c">##         yield (0,0)</span>
    <span class="c">##     elif x-min &gt;= 0:</span>
    <span class="c">##         for y in xrange(min, x-min+1):</span>
    <span class="c">##             yield (y, x-y)</span>
    <span class="c">## for (g1, g2) in add_up_to(g, min=0):</span>
    <span class="c">##     for (n1, n2) in add_up_to(n+1, min=1):</span>
    <span class="c">##         if (g1, n1) &lt; (0, 3) or (g2, n2) &lt; (0,3):</span>
    <span class="c">##             continue</span>
    <span class="c">##         for G1 in MgnTrivalentGraphsRecursiveGenerator(g1,n1):</span>
    <span class="c">##             for G2 in MgnTrivalentGraphsRecursiveGenerator(g2,n2):</span>
    <span class="c">##                 for x1 in G1.edge_orbits():</span>
    <span class="c">##                     for x2 in G2.edge_orbits():</span>
    <span class="c">##                         yield Fatgraph.bridge2(G1, x1, 0, G2, x2, 0)</span>
    <span class="c">##                         yield Fatgraph.bridge2(G1, x1, 0, G2, x2, 1)</span>
    <span class="c">##                         yield Fatgraph.bridge2(G1, x1, 1, G2, x2, 0)</span>
    <span class="c">##                         yield Fatgraph.bridge2(G1, x1, 1, G2, x2, 1)</span>




<div class="viewcode-block" id="MgnGraphsIterator"><a class="viewcode-back" href="../../api.html#fatghol.rg.MgnGraphsIterator">[docs]</a><span class="k">class</span> <span class="nc">MgnGraphsIterator</span><span class="p">(</span><span class="n">BufferingIterator</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;Iterate over all connected fatgraphs having the</span>
<span class="sd">    prescribed genus `g` and number of boundary cycles `n`.</span>
<span class="sd">    </span>
<span class="sd">    Examples::</span>

<span class="sd">      &gt;&gt;&gt; for g in MgnGraphsIterator(0,3): print g</span>
<span class="sd">      Fatgraph([Vertex([1, 2, 1]), Vertex([2, 0, 0])]) </span>
<span class="sd">      Fatgraph([Vertex([1, 0, 2]), Vertex([2, 0, 1])])</span>
<span class="sd">      Fatgraph([Vertex([1, 1, 0, 0])])</span>

<span class="sd">      &gt;&gt;&gt; for g in MgnGraphsIterator(1,1): print g</span>
<span class="sd">      Fatgraph([Vertex([1, 0, 2]), Vertex([2, 1, 0])])</span>
<span class="sd">      Fatgraph([Vertex([1, 0, 1, 0])])</span>

<span class="sd">    &quot;&quot;&quot;</span>

    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">g</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
        <span class="k">assert</span> <span class="n">n</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">,</span> \
               <span class="s">&quot;MgnGraphsIterator: &quot;</span> \
               <span class="s">&quot; number of boundary cycles `n` must be positive,&quot;</span>\
               <span class="s">&quot; but got `</span><span class="si">%s</span><span class="s">` instead&quot;</span> <span class="o">%</span> <span class="n">n</span>
        <span class="k">assert</span> <span class="p">(</span><span class="n">g</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span> <span class="ow">or</span> <span class="p">(</span><span class="n">g</span> <span class="o">==</span> <span class="mi">0</span> <span class="ow">and</span> <span class="n">n</span> <span class="o">&gt;=</span> <span class="mi">3</span><span class="p">),</span> \
               <span class="s">&quot;MgnGraphsIterator: &quot;</span> \
               <span class="s">&quot; Invalid (g,n) pair (</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">): &quot;</span>\
               <span class="s">&quot; need either g&gt;0 or g==0 and n&gt;2&quot;</span> \
               <span class="o">%</span> <span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">)</span>

        <span class="c">#: Prescribed genus of returned graphs</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">g</span> <span class="o">=</span> <span class="n">g</span>

        <span class="c">#: Prescribed number of boundary components</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">n</span> <span class="o">=</span> <span class="n">n</span>
        
        <span class="c"># Gather all 3-valent graphs.</span>
        <span class="n">timing</span><span class="o">.</span><span class="n">start</span><span class="p">(</span><span class="s">&quot;MgnGraphsIterator: trivalent graphs&quot;</span><span class="p">)</span>
        <span class="n">trivalent</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">MgnTrivalentGraphsRecursiveGenerator</span><span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
        <span class="n">timing</span><span class="o">.</span><span class="n">stop</span><span class="p">(</span><span class="s">&quot;MgnGraphsIterator: trivalent graphs&quot;</span><span class="p">)</span>

        <span class="c">#: Fatgraphs to be contracted at next `.refill()` invocation</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_batch</span> <span class="o">=</span> <span class="n">trivalent</span>

        <span class="c">#: Graphs returned by next `.refill()` call will have this</span>
        <span class="c">#  number of vertices.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span> <span class="o">=</span> <span class="mi">4</span><span class="o">*</span><span class="n">g</span> <span class="o">+</span> <span class="mi">2</span><span class="o">*</span><span class="n">n</span> <span class="o">-</span> <span class="mi">5</span>
        
        <span class="c"># initialize superclass with list of trivalent graphs</span>
        <span class="n">BufferingIterator</span><span class="o">.</span><span class="n">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">trivalent</span><span class="p">)</span>
        <span class="n">logging</span><span class="o">.</span><span class="n">info</span><span class="p">(</span><span class="s">&quot;  Found </span><span class="si">%d</span><span class="s"> distinct unique trivalent fatgraphs. (Elapsed: </span><span class="si">%.3f</span><span class="s">s)&quot;</span><span class="p">,</span>
                     <span class="nb">len</span><span class="p">(</span><span class="n">trivalent</span><span class="p">),</span> <span class="n">timing</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s">&quot;MgnGraphsIterator: trivalent graphs&quot;</span><span class="p">))</span>


    <span class="k">def</span> <span class="nf">refill</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">StopIteration</span>

        <span class="k">try</span><span class="p">:</span>
            <span class="n">checkpoint</span> <span class="o">=</span> <span class="n">os</span><span class="o">.</span><span class="n">path</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">runtime</span><span class="o">.</span><span class="n">options</span><span class="o">.</span><span class="n">checkpoint_dir</span><span class="p">,</span>
                                      <span class="p">(</span><span class="s">&quot;M</span><span class="si">%d</span><span class="s">,</span><span class="si">%d</span><span class="s">-MgnGraphsIterator</span><span class="si">%d</span><span class="s">.list&quot;</span>
                                       <span class="o">%</span> <span class="p">(</span><span class="n">runtime</span><span class="o">.</span><span class="n">g</span><span class="p">,</span> <span class="n">runtime</span><span class="o">.</span><span class="n">n</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span><span class="p">)))</span>
        <span class="k">except</span> <span class="ne">AttributeError</span><span class="p">:</span>
            <span class="c"># running a test, so no `runtime.options` defined</span>
            <span class="n">checkpoint</span> <span class="o">=</span> <span class="bp">None</span>

        <span class="c"># try loading `next_batch` from old persisted state</span>
        <span class="n">next_batch</span> <span class="o">=</span> <span class="bp">None</span>
        <span class="k">if</span> <span class="n">checkpoint</span> <span class="ow">and</span> <span class="n">runtime</span><span class="o">.</span><span class="n">options</span><span class="o">.</span><span class="n">restart</span><span class="p">:</span>
            <span class="k">try</span><span class="p">:</span>
                <span class="n">next_batch</span> <span class="o">=</span> <span class="n">load</span><span class="p">(</span><span class="n">checkpoint</span><span class="p">)</span>
                <span class="k">if</span> <span class="n">next_batch</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
                    <span class="n">logging</span><span class="o">.</span><span class="n">info</span><span class="p">(</span><span class="s">&quot;  Loaded graphs with </span><span class="si">%d</span><span class="s"> vertices from file &#39;</span><span class="si">%s</span><span class="s">&#39;&quot;</span><span class="p">,</span>
                                 <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span><span class="p">,</span> <span class="n">checkpoint</span><span class="p">)</span>
            <span class="k">except</span> <span class="ne">Exception</span><span class="p">,</span> <span class="n">error</span><span class="p">:</span>
                <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;  Could not retrieve state from file &#39;</span><span class="si">%s</span><span class="s">&#39;: </span><span class="si">%s</span><span class="s">&quot;</span><span class="p">,</span>
                              <span class="n">checkpoint</span><span class="p">,</span> <span class="n">error</span><span class="o">.</span><span class="n">message</span><span class="p">)</span>
                <span class="c"># ignore error, continue generating graphs</span>

        <span class="k">if</span> <span class="n">next_batch</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
            <span class="c"># really compute `next_batch`</span>
            <span class="n">logging</span><span class="o">.</span><span class="n">debug</span><span class="p">(</span><span class="s">&quot;Generating graphs with </span><span class="si">%d</span><span class="s"> vertices ...&quot;</span><span class="p">,</span>
                         <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span><span class="p">)</span>
            <span class="n">discarded</span> <span class="o">=</span> <span class="mi">0</span>
            <span class="n">next_batch</span> <span class="o">=</span> <span class="p">[]</span>
            <span class="n">timing</span><span class="o">.</span><span class="n">start</span><span class="p">(</span><span class="s">&quot;MgnGraphsIterator: </span><span class="si">%d</span><span class="s"> vertices&quot;</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span><span class="p">)</span>
            <span class="k">for</span> <span class="n">graph</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_batch</span><span class="p">:</span>
                <span class="c"># contract all edges</span>
                <span class="k">for</span> <span class="n">edge</span> <span class="ow">in</span> <span class="n">graph</span><span class="o">.</span><span class="n">edge_orbits</span><span class="p">():</span>
                    <span class="k">if</span> <span class="ow">not</span> <span class="n">graph</span><span class="o">.</span><span class="n">is_loop</span><span class="p">(</span><span class="n">edge</span><span class="p">):</span>
                        <span class="n">dg</span> <span class="o">=</span> <span class="n">graph</span><span class="o">.</span><span class="n">contract</span><span class="p">(</span><span class="n">edge</span><span class="p">)</span>
                        <span class="k">if</span> <span class="n">dg</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">next_batch</span><span class="p">:</span>
                            <span class="c"># put graph back into next batch for processing</span>
                            <span class="n">next_batch</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">dg</span><span class="p">)</span>
                        <span class="k">else</span><span class="p">:</span>
                            <span class="n">discarded</span> <span class="o">+=</span> <span class="mi">1</span>
            <span class="n">timing</span><span class="o">.</span><span class="n">stop</span><span class="p">(</span><span class="s">&quot;MgnGraphsIterator: </span><span class="si">%d</span><span class="s"> vertices&quot;</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span><span class="p">)</span>
            <span class="n">logging</span><span class="o">.</span><span class="n">info</span><span class="p">(</span><span class="s">&quot;  Found </span><span class="si">%d</span><span class="s"> distinct unique fatgraphs with </span><span class="si">%d</span><span class="s"> vertices, discarded </span><span class="si">%d</span><span class="s"> duplicates. (Elapsed: </span><span class="si">%.3f</span><span class="s">s)&quot;</span><span class="p">,</span>
                         <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_batch</span><span class="p">),</span> <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span><span class="p">,</span> <span class="n">discarded</span><span class="p">,</span>
                         <span class="n">timing</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s">&quot;MgnGraphsIterator: </span><span class="si">%d</span><span class="s"> vertices&quot;</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span><span class="p">))</span>
            <span class="k">if</span> <span class="n">checkpoint</span> <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
                <span class="n">save</span><span class="p">(</span><span class="n">next_batch</span><span class="p">,</span> <span class="n">checkpoint</span><span class="p">)</span>
                
        <span class="bp">self</span><span class="o">.</span><span class="n">_batch</span> <span class="o">=</span> <span class="n">next_batch</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_num_vertices</span> <span class="o">-=</span> <span class="mi">1</span>
        <span class="k">return</span> <span class="n">next_batch</span>



<span class="c">## main: run tests</span>
</div>
<span class="k">if</span> <span class="s">&quot;__main__&quot;</span> <span class="o">==</span> <span class="n">__name__</span><span class="p">:</span>
    <span class="kn">import</span> <span class="nn">doctest</span>
    <span class="n">doctest</span><span class="o">.</span><span class="n">testmod</span><span class="p">(</span><span class="n">name</span><span class="o">=</span><span class="s">&#39;rg&#39;</span><span class="p">,</span>
                    <span class="n">optionflags</span><span class="o">=</span><span class="n">doctest</span><span class="o">.</span><span class="n">NORMALIZE_WHITESPACE</span><span class="p">)</span>
</pre></div>

          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
<div id="searchbox" style="display: none">
  <h3>Quick search</h3>
    <form class="search" action="../../search.html" method="get">
      <input type="text" name="q" size="18" />
      <input type="submit" value="Go" />
      <input type="hidden" name="check_keywords" value="yes" />
      <input type="hidden" name="area" value="default" />
    </form>
    <p class="searchtip" style="font-size: 90%">
    Enter search terms or a module, class or function name.
    </p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li><a href="../../index.html">FatGHoL v5.4 documentation</a> &raquo;</li>
          <li><a href="../index.html" >Module code</a> &raquo;</li> 
      </ul>
    </div>

    <div class="footer">
        &copy; Copyright 2012, Riccardo Murri.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.0.7.
    </div>
<div class="footer">This page uses <a href="http://analytics.google.com/">
Google Analytics</a> to collect statistics. You can disable it by blocking
the JavaScript coming from www.google-analytics.com.
<script type="text/javascript">
  (function() {
    var ga = document.createElement('script');
    ga.src = ('https:' == document.location.protocol ?
              'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
    ga.setAttribute('async', 'true');
    document.documentElement.firstChild.appendChild(ga);
  })();
</script>
</div>

  </body>
</html>